ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Routing Tables

Time limit: 2.0 second
Memory limit: 64 MB
Routers are special devices used to forward data packets in modern computer networks. The behavior of a router is defined by a routing table. This table consists of several lines each of which contains the IP address of a destination network d, a mask m, and the IP address of a gateway g. For example, the line “” means that a packet addressed to network with mask should be forwarded through gateway
An IP address is a 32-bit integer, which is divided for convenience into four bytes. The value of each byte is written in decimal notation and these values are separated by dots. For example, the notation means the binary number 11000000101010000001100000000000. Masks are written similarly; moreover, the binary representation of a mask is started with ones only, which are followed by zeros only.
The algorithm of choosing a route is as follows. Consider a packet sent to address a. The router selects form the table all the lines satisfying the condition d and m = a and m (`and' is the bitwise AND operation). A line with the maximal number of ones in the mask is then chosen from these lines and the packet is sent to the gateway specified in this line. It is guaranteed that there is at most one such line for any destination address.
Two routing tables are equivalent if a packet with any destination address will be sent to the same gateway (or will not be sent at all) according to these tables. The following routing tables are equivalent:

Write a program to check if two routing tables are equivalent.


The first line contains the number of lines in the first routing table. This table is given in the following lines in the format described above. Then follows the second routing table in the same format. The total number of lines in these tables doesn't exceed 65536.


If the tables are equivalent, output “YES”. Otherwise, output “NO”.



Problem Author: Igor Andrianov
Problem Source: XII USU Open Personal Contest (March 19, 2011)
To submit the solution for this problem go to the Problem set: 1829. Routing Tables