The Great Amu
Practice
4.3 (13 votes)
Mathematics
Modular exponentiation
Hard
Modular arithmetic
Number theory
Problem
83% Success 124 Attempts 50 Points 3s Time Limit 256MB Memory 1024 KB Max Code

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).

Input

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).

Output

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

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
36 votes
Tags:
Ad-HocAlgorithmsApprovedBasic ProgrammingEasyImplementationOpen
Points:50
1 votes
Tags:
Segment treeAdvanced Data StructuresSegment TreesData Structures
Points:50
5 votes