Problem A
Election Security
Elections Canada has decided to add a security code at the bottom of each of its ballots to help distinguish valid ballots from invalid (fraudulent) ballots. These codes must differ from region to region, and election officials in each region have been given the responsibility of designing the codes for their region. The Atlantic Canadian Polling Commission (ACPC), after consulting with local computer science faculty, has decided that its codes will be strings of $\textrm{base-}10$ digits that satisfy certain criteria. The new ballot design requires that two lines be printed at the bottom of each ballot:
-
The first line contains three integers: a base $(b)$, a modulus $(m)$, and a remainder $(r)$.
-
The second line contains the security code.
These are the criteria established by the ACPC for the security code:
-
Every digit in the code is a legal $\textrm{base-}b$ digit, i.e., is in $\{ 0, 1, \dots , (b-1)\} $.
-
The code can be written as the concatenation of one or more $\textrm{base-}b$ numbers, each of which is congruent to $r$ $(\textrm{mod }m)$. Note that except for the number $0$ itself, a $\textrm{base-}b$ number must begin with a nonzero digit.
A code that satisfies these two criteria is valid; otherwise, it is invalid. Your job is to write a program that distinguishes between valid codes and invalid codes.
Input
The first line of input contains an integer, $n$ $(1 \leq n \leq 5\, 000)$, the number of test cases. Each test case consists of two lines with the information written at the bottom of a ballot. The first of these two lines contains three space-separated integers, $b$, $m$, $r$, with $2 \leq b \leq 10$, $2 \leq m \leq 1\, 000$, and $0 \leq r < m$. The second of these two lines contains a code to be tested for validity, a string of $\textrm{base-}10$ digits with length between $1$ and $100\, 000$, inclusive. The total number of digits in all $n$ codes combined is at most $100\, 000$.
Output
For each test case, output a single line containing “valid” if the code is valid, or “invalid” if the code is invalid.
Explanation of Sample Input/Output 1
Here we use $N_{(b)}$ to indicate a number $N$ written in $\textrm{base }b$, and we convert to $\textrm{base }10$ (if necessary) for clarity. For example, the equation $746_{(8)} = 486_{(10)}$ says that the $\textrm{base-}8$ number $746$ is equal to $486$ when written in $\textrm{base }10$. In the first test case, $530_{(7)} = 266_{(10)}$, which is congruent to $2$ $(\textrm{mod }4)$, so the code is valid. In the second test case, $3535_{(7)} = 1300_{(10)}$, which is congruent to $0$, not $2$ $(\textrm{mod }4)$. However, $3535$ can be written as the concatenation of $35$ and $35$, each of which is congruent to $2$ $(\textrm{mod }4)$ (since $35_{(7)} = 26_{(10)}$), so the code is valid. In the third test case, $875_{(10)}$ is not congruent to $3$ $(\textrm{mod }6)$, and it is not possible to partition $875$ into smaller numbers that are all congruent to $3$ $(\textrm{mod }6)$, so the code is invalid. (One (failed) attempt is $87|5$: $87$ is congruent to $3$ $(\textrm{mod }6)$, but $5$ is not.)
| Sample Input 1 | Sample Output 1 |
|---|---|
3 7 4 2 530 7 4 2 3535 10 6 3 875 |
valid valid invalid |
