ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

H. 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
To submit the solution for this problem go to the Problem set: 1487. Chinese Football