Sergey and Denis have decided that when they are free from contests, table-football matches, and watching movies, they will visit one of the many sport bars of Petrozavodsk. The point is that just during the work of the training camp a round of the Chinese Football Championship is held. Sergey and Denis want to watch the most interesting matches of the championship. There are N teams playing in the Chinese Football Championship. Each team will play with each exactly once. Despite roaring passions on the stands, the championship is rather dull: if a team A has beaten a team B, and the team B has beaten a team C, then either A has already beaten C or A will necessarily beat C. In this case we say that the team A is stronger than the teams B and C (more formally, A is stronger than B if A has beaten B or if A has beaten a team C which is stronger than B). There are no draws in the championship.
Denis and Sergey have an argument about which of two Chinese teams plays football better. Denis claims that the “Katraps” team plays better than the “Kolomotiv” team, namely, that “Katraps” is not weaker than any team which is stronger than “Komolotiv”. Help them to resolve this argument. Your task is to determine for a given pair of teams whether the first team plays better than the second one. Here the term “plays better” is understood in the same way as Denis understands it. It is assumed that a team A is not weaker that a team B if at the moment it cannot be said that B is stronger than A.
The first line contains the number of teams participating in the championship N (2 ≤ N ≤ 1000).
The teams are numbered from 1 to N. In the next N
lines, results of matches are given. Each of these lines contains N symbols. If the ith and jth teams have already played with each other and the ith team has won, then there is the number 1 in the jth position of the ith line. In other cases, there are zeros. The next line contains the number of queries Q ≤ 50000. The queries are given in the following Q lines in the form A B (1 ≤ A, B ≤ N; A ≠ B).
For each query, output “YES” if the team A plays better than the team B, otherwise output “No”.
Problem Author: Sergey Pupyrev
Problem Source: The XIth USU Programing Championship, October 7, 2006