All Tracks Problem

The Great Amu

Mathematics, Modular arithmetic, Modular exponentiation, Number Theory


View Russian Translation

The great Amu is the the special agent chosen directly from by the king.

There are n cities in his country. There are n businessmen in his country, i-th living in city number i. Every year, businessman number j should pay exactly wi,j times xj dollars to the mayor of city number i as tax, which xj is the number of clients he had that year (which is always a non-negative integer).

Each year, it's Amu's duty that at the end of each year ask each mayor what's the value of amount money he received that year, modulo 7190; And then check if it's possible that they're all telling the truth (there is a valid vector x' consisting of n non-negative integers, such that if for each valid i, xi = x'i, then all of the numbers the mayors said are correct).

There are q years left of Amu's service and he has no idead what to do. So that's your duty to each year tell the king if it's possible all mayors all telling the truth or not (a single Yes or No each year).


The first line of input contains two integers n and q (1 ≤ n, q ≤ 300).

The next n lines contain the matrix w. i-th lines contains integers wi,1, wi,2, ..., wi,n (0 ≤ wi,j < 7190).

The next q lines contain the numbers mayors all telling for each year. Each line contains n integers y1, y2, ..., yn where yi is the number i-th mayor told Amu (remainder of money he received thay year, after dividing by 7190) (0 ≤ yi < 7190).


For each year, print a single word, "Yes" or "No" (without quotes) in one line.

5 3
16 12 13 17 19
1 8 17 15 1
14 14 11 17 11
7 2 10 4 17
7 9 0 9 19
7 9 13 2 14
15 17 16 17 16
269 91 229 139 149
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications