LCC/Moose '20 Contest 2 J4 - IPv5

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Chris is developing a new standard for IP addresses on the internet called IPv5. In IPv5, addresses are formatted in blocks, with the form being x_0.x_1.x_2...x_{N-1}. Depending on the implementation, the number of blocks in the IPv5 addresses can change. Every x_i in an IPv5 address is between 0 and 255, inclusive.

An IPv5 address a is less than another address b if

  • a_0 < b_1 OR
  • a_0 = b_0 and a_1 < b_1 OR
  • a_0 = b_0 and a_1 = b_1 and a_2 < b_2 OR

    ...

  • a_0 = b_0 and a_1 = b_1 and a_2 = b_2 ... a_{N-1} < b_{N-1}

You are given M inclusive IPv5 address ranges formatted in form a-b and K IPv5 addresses.

Determine the number of IPv5 addresses that are in any of the ranges.

Input Specification

The first line of input will consist of a single integer, N (1 \leq N \leq 100) representing the number of blocks in the IPv5 address.

The next line of input will consist of a single integer, M (0 \leq M \leq 100) representing the number of IPv5 ranges you will be given.

The next M lines of input will consist of valid IPv5 ranges in form a-b (a < b).

The next line of input will consist of a single integer, K (0 \leq K \leq 100) representing the number of IPv5 addresses you have to check.

The next K lines of input will consist of a single IPv5 address.

Output Specification

Your output should consist of a single integer, the number of IP addresses that are within any of the ranges.

Sample Input

5
2
0.0.0.0.1-0.0.1.0.0
1.1.1.0.0-1.1.1.1.1
2
0.0.0.0.0
1.1.1.1.1

Sample Output

1

Sample Explanation

1.1.1.1.1 is between 1.1.1.0.0-1.1.1.1.1.


Comments

There are no comments at the moment.