Problem Statement

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

Uppercase each character of S and print the resulting string T.

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Problem Statement

There are N bridges in AtCoder Village. The height of the bridge numbered i is H_i (i is an integer between 1 and N).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

• 1\leq N \leq 100
• 1\leq H_i \leq 10^9
• All H_i are different.
• All values in the input are integers.

Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of 50, 80, and 70, respectively, so the second bridge is the highest.
Thus, 2 should be printed.

Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.

Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of 97) is the highest.

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
• (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• 1 \le N \le 10
• 1 \le A_{i,j} \le 9
• All values in input are integers.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

Problem Statement

In this problem, an input file contains multiple test cases.
You are first given an integer T. Solve the following problem for T test cases.

• We have N positive integers A_1, A_2, ..., A_N. How many of them are odd?

Constraints

• 1 \leq T \leq 100
• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3
1 2 3
2
20 23
10
6 10 4 1 5 9 8 6 5 1
1
1000000000

Sample Output 1

2
1
5
0

This input contains four test cases.

The second and third lines correspond to the first test case, where N = 3, A_1 = 1, A_2 = 2, A_3 = 3.
We have two odd numbers in A_1, A_2, and A_3, so the first line should contain 2.

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

Constraints

• -10^9 \leq x_1 \leq 10^9
• -10^9 \leq y_1 \leq 10^9
• -10^9 \leq x_2 \leq 10^9
• -10^9 \leq y_2 \leq 10^9
• (x_1, y_1) \neq (x_2, y_2)
• All values in input are integers.

Sample Input 1

0 0 3 3

Sample Output 1

Yes

• The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
• the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
• point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.

Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.

Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

• P is a permutation of (1, \dots, N).
• For every pair of integers i, j between 1 and N (inclusive), the following holds.
  • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
• (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

Sample Input 2

5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

Problem Statement

Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.

Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.

Constraints

• 1\leq N\leq 50
• 1\leq X\leq 10^4
• 1\leq A_i\leq 100
• 1\leq B_i\leq 50
• A_i are pairwise distinct.
• All values in the input are integers.

Sample Input 1

2 19
2 3
5 6

Sample Output 1

Yes

Takahashi has three 2-yen coins and six 5-yen coins. He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen. Thus, Yes should be printed.

Sample Input 2

2 18
2 3
5 6

Sample Output 2

No

There is no combination of the coins that he can use to pay exactly 18 yen. Thus, No should be printed.

Sample Input 3

3 1001
1 1
2 1
100 10

Sample Output 3

Yes

He need not use all kinds of coins.

Problem Statement

We have a simple undirected graph with N vertices and M edges. The vertices are numbered 1,\ldots,N. For each i=1,\ldots,M, the i-th edge connects Vertex a_i and Vertex b_i. Additionally, the degree of each vertex is at most 3.

For each i=1,\ldots,Q, answer the following query.

• Find the sum of indices of vertices whose distances from Vertex x_i are at most k_i.

Constraints

• 1 \leq N \leq 1.5 \times 10^5
• 0 \leq M \leq \min (\frac{N(N-1)}{2},\frac{3N}{2})
• 1 \leq a_i \lt b_i \leq N
• (a_i,b_i) \neq (a_j,b_j), if i\neq j.
• The degree of each vertex in the graph is at most 3.
• 1 \leq Q \leq 1.5 \times 10^5
• 1 \leq x_i \leq N
• 0 \leq k_i \leq 3
• All values in input are integers.

Sample Input 1

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

Sample Output 1

1
20
2
20
7
6
20

For the 1-st query, the only vertex whose distance from Vertex 1 is at most 1 is Vertex 1, so the answer is 1.
For the 2-nd query, the vertices whose distances from Vertex 2 are at most 2 are Vertex 2, 3, 4, 5, and 6, so the answer is their sum, 20.
The 3-rd and subsequent queries can be answered similarly.

Problem Statement

We have a typewriter with N rows. The keys in the i-th row from the top can type the characters in a string S_i.

Let us use this keyboard to enter a string, as follows.

• First, choose an integer 1 \le k \le N.
• Then, start with an empty string and only use the keys in the k-th row from the top to enter a string of length exactly L.

How many strings of length L can be entered in this way? Since the answer can be enormous, print it modulo 998244353.

Constraints

• N and L are integers.
• 1 \le N \le 18
• 1 \le L \le 10^9
• S_i is a (not necessarily contiguous) non-empty subsequence of abcdefghijklmnopqrstuvwxyz.

Sample Input 1

2 2
ab
ac

Sample Output 1

7

We can enter seven strings: aa, ab, ac, ba, bb, ca, cc.

Sample Input 2

4 3
abcdefg
hijklmnop
qrstuv
wxyz

Sample Output 2

1352

Sample Input 3

5 1000000000
abc
acde
cefg
abcfh
dghi

Sample Output 3

346462871

Be sure to print the answer modulo 998244353.