Problem Statement

You are given positive integers X,Y,Z.

Takahashi and Aoki are currently X years old and Y years old, respectively.

Takahashi and Aoki age by 1 year simultaneously on every January 1st.

Determine whether there is a moment in the future (including this year) when Takahashi's age becomes exactly Z times Aoki's age.

Constraints

• 1\le X,Y \le 100
• 2\le Z\le 10
• All input values are integers.

Sample Input 1

44 20 2

Sample Output 1

Yes

Four years from now, Takahashi will be 48 years old and Aoki will be 24 years old, so Takahashi's age will be exactly twice Aoki's age. Thus, output Yes.

Sample Input 2

28 10 3

Sample Output 2

No

There will never be a moment when Takahashi's age becomes exactly three times Aoki's age. Thus, output No.

Sample Input 3

50 5 10

Sample Output 3

Yes

Currently, Takahashi's age is exactly 10 times Aoki's age.

Note that you need to determine whether there will be such a moment in the future including this year.

Sample Input 4

1 100 2

Sample Output 4

No

Problem Statement

There are N people standing in a row from left to right. The i-th person from the left (1\le i\le N) is called person i. The height of person i (1\le i\le N) is A_i.

For each i=1,2,\ldots,N, determine whether there exists a person to the left of person i who is taller than person i, and if so, find the person standing closest to person i among them.

Constraints

• 1\le N\le 100
• 1\le A_i\le 100
• All input values are integers.

Sample Input 1

4
4 3 2 5

Sample Output 1

-1
1
2
-1

• There is no person to the left of person 1. Thus, output -1 on the first line.
• Among the people to the left of person 2, only person 1 is taller than person 2. Thus, output 1 on the second line.
• Among the people to the left of person 3, persons 1,2 are taller than person 3, and the person standing closest to person 3 is person 2. Thus, output 2 on the third line.
• There is no person to the left of person 4 who is taller than person 4. Thus, output -1 on the fourth line.

Sample Input 2

3
7 7 7

Sample Output 2

-1
-1
-1

There may be multiple people with the same height.

Sample Input 3

6
31 9 17 10 2 9

Sample Output 3

-1
1
1
3
4
4

Problem Statement

You are given a string S consisting of digits.

A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem F.)

• T is a non-empty string consisting of digits.
• |T| is even, where |T| denotes the length of string T.
• All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
• All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
• Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.

For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.

Find the number of substrings of S that are 1122-strings.

Two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.

Constraints

• S is a string consisting of digits with length between 1 and 10^6, inclusive.

Sample Input 1

1122

Sample Output 1

2

The following two substrings satisfy the condition.

• 12 extracted from the 2-nd through 3-rd characters of S
• 1122 extracted from the 1-st through 4-th characters of S

Thus, output 2.

Sample Input 2

7788788

Sample Output 2

3

Note that two substrings are counted separately if they are extracted from different positions, even if they are identical as strings.

Sample Input 3

2025

Sample Output 3

0

There may be no substring that is a 1122-string.

Sample Input 4

1112222334445556555

Sample Output 4

11

Problem Statement

For positive integers x,y, define f(x,y) as follows:

• The value obtained by interpreting x,y in decimal notation without leading zeros as strings, concatenating them in this order to obtain a string S, and then interpreting S as an integer in decimal notation.

For example, f(12,3) = 123 and f(100,40)=10040.

You are given positive integers N,M and a sequence of N positive integers A=(A_1,A_2,\ldots,A_N).

Find the number of pairs of integers (i,j) that satisfy all of the following conditions.

• 1\le i,j\le N
• f(A_i,A_j) is a multiple of M.

Constraints

• 1\le N\le 2\times 10^5
• 1\le M\le 10^9
• 1\le A_i\le 10^9
• All input values are integers.

Sample Input 1

2 11
2 42

Sample Output 1

2

• When (i,j)=(1,1): f(A_1,A_1)=22 is a multiple of 11.
• When (i,j)=(1,2): f(A_1,A_2)=242 is a multiple of 11.
• When (i,j)=(2,1): f(A_2,A_1)=422 is not a multiple of 11.
• When (i,j)=(2,2): f(A_2,A_2)=4242 is not a multiple of 11.

From the above, the pairs of integers that satisfy all the conditions are (i,j)=(1,1),(1,2), which is two pairs. Thus, output 2.

Sample Input 2

4 7
2 8 16 183

Sample Output 2

4

Sample Input 3

5 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

25

Sample Input 4

12 13
80 68 862370 82217 8 56 5 168 672624 6 286057 11864

Sample Output 4

10

Problem Statement

You are given integers N,M, a sequence of N integers X=(X_1,X_2,\ldots,X_N), and a sequence of M integers Y=(Y_1,Y_2,\ldots,Y_M).

Determine whether there exists an N row by M column integer matrix A=(A_{i,j}) (1\le i\le N,\ 1\le j\le M) that satisfies all of the following conditions, and if so, find one such matrix.

• 1\le A_{i,j} \le N\times M
• All N\times M elements of A_{i,j} are distinct.
• \displaystyle \max_{1\le j\le M} A_{i,j} = X_i for i=1,2,\ldots,N.
• \displaystyle \max_{1\le i\le N} A_{i,j} = Y_j for j=1,2,\ldots,M.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 10^5
• 1\le N,M
• The sum of N\times M over all test cases is at most 2\times 10^5.
• 1\le X_i,Y_j\le N\times M
• All input values are integers.

Sample Input 1

3
2 3
5 6
5 3 6
3 3
5 4 6
6 2 4
5 4
18 20 19 14 17
18 20 14 15

Sample Output 1

Yes
5 1 4
2 3 6
No
Yes
18 12 4 9
13 20 1 10
16 19 6 8
2 5 14 3
11 17 7 15

Consider the first test case.

In the sample output, all elements of A are between 1 and 6 and are distinct, and furthermore,

• \displaystyle \max_{1\le j\le 3} A_{1,j} =\max \lbrace 5,1,4\rbrace = 5 = X_1
• \displaystyle\max_{1\le j\le 3} A_{2,j} =\max \lbrace 2,3,6\rbrace = 6 = X_2
• \displaystyle\max_{1\le i\le 2} A_{i,1} =\max \lbrace 5,2\rbrace = 5 = Y_1
• \displaystyle\max_{1\le i\le 2} A_{i,2} =\max \lbrace 1,3\rbrace = 3 = Y_2
• \displaystyle\max_{1\le i\le 2} A_{i,3} =\max \lbrace 4,6\rbrace = 6 = Y_3

so all conditions are satisfied.

Other outputs, such as the following, are also accepted.

Yes
5 3 1
4 2 6

Problem Statement

You are given a string S consisting of digits.

A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem C.)

• T is a non-empty string consisting of digits.
• |T| is even, where |T| denotes the length of string T.
• All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
• All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
• Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.

For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.

Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of S that are 1122-strings.

Two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Constraints

• S is a string consisting of digits with length between 1 and 10^6, inclusive.

Sample Input 1

1122

Sample Output 1

5

The following five subsequences satisfy the condition.

• 12 extracted from the 1-st and 3-rd characters of S
• 12 extracted from the 1-st and 4-th characters of S
• 12 extracted from the 2-nd and 3-rd characters of S
• 12 extracted from the 2-nd and 4-th characters of S
• 1122 extracted from the 1-st through 4-th characters of S

Thus, output 5.

Note that two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Sample Input 2

2025

Sample Output 2

0

There may be no subsequence that is a 1122-string.

Sample Input 3

0777468889971

Sample Output 3

30

Problem Statement

You are given a string S consisting of lowercase English letters.

Alice and Bob play the following game using this string.

• Prepare an empty string T.
• Starting with Alice, they take turns playing.
• On each turn, the player chooses one lowercase English letter and concatenates the chosen letter to the end of T. Here, the player cannot take an action such that T after concatenation is not a substring of S.

The player who cannot make a move first loses.

Determine which player will win when both players play optimally.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 10^5
• T is an integer.
• S is a string consisting of lowercase English letters with length between 1 and 2\times 10^5, inclusive.
• The sum of the lengths of S over all test cases is at most 4\times 10^5.

Sample Input 1

4
ooxo
abrakadabra
atcoderbeginnercontest
baabca

Sample Output 1

Bob
Alice
Alice
Bob

Consider the first test case.

For example, the game proceeds as follows.

• Alice chooses x. T= x.
• Bob chooses o. T= xo.
• No matter which lowercase English letter Alice chooses and concatenates to the end of T, T will not be a substring of S, so Alice cannot make a move. At this point, Bob wins.

In this test case, Bob can win no matter how Alice plays. Therefore, output Bob.