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

1487. Chinese Football

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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 ≤ AB ≤ N; A ≠ B).

Output

For each query, output “YES” if the team A plays better than the team B, otherwise output “No”.

Sample

inputoutput
3
011
000
000
2
2 3
1 3
No
YES
Problem Author: Sergey Pupyrev
Problem Source: The XIth USU Programing Championship, October 7, 2006