Problem Statement

In the hexadecimal system, where the digits ABCDEF corresponding to 10,11,12,13,14, and 15 are used in addition to 0123456789, every integer between 0 and 255 is represented as a 1- or 2-digit numeral.
For example, 0 and 12 are represented as 1-digit hexadecimal numerals 0 and C; 99 and 255 are represented as 2-digit hexadecimals 63 and FF.

Given an integer N between 0 and 255, convert it to an exactly two-digit hexadecimal numeral, prepending leading 0s if necessary.

Notes

The judge is case-sensitive. Specifically, you cannot use abcdef as hexadecimal digits instead of ABCDEF.

Constraints

• 0 \leq N \leq 255
• N is an integer.

Sample Input 1

99

Sample Output 1

63

99 is represented as 63 in hexadecimal.

Sample Input 2

12

Sample Output 2

0C

12 is represented as C in hexadecimal.
Since we ask you to convert it to a two-digit hexadecimal numeral, the answer is 0C, where 0 is prepended to C.

Sample Input 3

0

Sample Output 3

00

Sample Input 4

255

Sample Output 4

FF

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• L_i \geq 1 \, (1 \leq i \leq N)
• \sum_{i=1}^N L_i \leq 2 \times 10^5
• 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
• 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
• All values in the input are integers.

Sample Input 1

2 2
3 1 4 7
2 5 9
1 3
2 1

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

• The 3-rd term of the 1-st sequence is 7.
• The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

128
1
26535
901

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

There are N cards with an integer written on each side. Card i (1 \leq i \leq N) has an integer a_i written on the front and an integer b_i written on the back.

You may choose whether to place each card with its front or back side visible.

Determine if you can place the cards so that the sum of the visible integers exactly equals S. If possible, find a placement of the cards to realize it.

Constraints

• 1 \leq N \leq 100
• 1 \leq S \leq 10000
• 1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)
• All values in the input are integers.

Sample Input 1

3 11
1 4
2 3
5 7

Sample Output 1

Yes
THH

For example, the following placements make the sum of the visible integers exactly equal S (= 11):

• Place the 1-st card with its front side visible, 2-nd with its back, and 3-rd with its back.
• Place the 1-st card with its back side visible, 2-nd with its front, and 3-rd with its front.

Therefore, outputs like HTT and THH are accepted.

Sample Input 2

5 25
2 8
9 3
4 11
5 1
12 6

Sample Output 2

No

You cannot place the cards so that the sum of the visible integers exactly equals S (= 25).

Problem Statement

There are N towns numbered 1, \dots, N, and M roads numbered 1, \dots, M.
Every road is directed; road i (1 \leq i \leq M) leads you from Town A_i to Town B_i. The length of road i is C_i.

You are given a sequence E = (E_1, \dots, E_K) of length K consisting of integers between 1 and M. A way of traveling from town 1 to town N using roads is called a good path if:

• the sequence of the roads' numbers arranged in the order used in the path is a subsequence of E.

Note that a subsequence of a sequence is a sequence obtained by removing 0 or more elements from the original sequence and concatenating the remaining elements without changing the order.

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, report that fact.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M, K \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)
• 1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)
• 1 \leq E_i \leq M \, (1 \leq i \leq K)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4

There are two possible good paths as follows:

• Using road 4. In this case, the sum of the length of the used road is 5.
• Using road 1 and 2 in this order. In this case, the sum of the lengths of the used roads is 2 + 2 = 4.

Therefore, the desired minimum value is 4.

Sample Input 2

3 2 3
1 2 1
2 3 1
2 1 1

Sample Output 2

-1

There is no good path.

Sample Input 3

4 4 5
3 2 2
1 3 5
2 4 7
3 4 10
2 4 1 4 3

Sample Output 3

14

Problem Statement

There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.

When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.

Constraints

• 2 \leq N \leq 20
• 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
• All values in the input are integers.

Sample Input 1

3
1 5 2
7 0 5
4 2 3

Sample Output 1

2

The following two ways satisfy the condition:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).

Sample Input 2

2
1 2
2 1

Sample Output 2

0

Sample Input 3

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

Sample Output 3

24307

Problem Statement

Takahashi has decided to put a web counter on his webpage.
The accesses to his webpage are described as follows:

• For i=0,1,2,\ldots,23, there is a possible access at i o'clock every day:
  • If c_i=T, Takahashi accesses the webpage with a probability of X percent.
  • If c_i=A, Aoki accesses the webpage with a probability of Y percent.
  • Whether or not Takahashi or Aoki accesses the webpage is determined independently every time.
• There is no other access.

Also, Takahashi believes it is preferable that the N-th access since the counter is put is not made by Takahashi himself.

If Takahashi puts the counter right before 0 o'clock of one day, find the probability, modulo 998244353, that the N-th access is made by Aoki.

Notes

We can prove that the sought probability is always a finite rational number. Moreover, under the constraints of this problem, when the value is represented as \frac{P}{Q} with two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq X,Y \leq 99
• c_i is T or A.
• N, X, and Y are integers.

Sample Input 1

1 50 50
ATATATATATATATATATATATAT

Sample Output 1

665496236

The 1-st access since Takahashi puts the web counter is made by Aoki with a probability of \frac{2}{3}.

Sample Input 2

271 95 1
TTTTTTTTTTTTTTTTTTTTTTTT

Sample Output 2

0

There is no access by Aoki.

Sample Input 3

10000000000000000 62 20
ATAATTATATTTAAAATATTATAT

Sample Output 3

744124544

Problem Statement

Solve the following problem for T test cases.

A piece is placed at the origin (0, 0) on an xy-plane. You may perform the following operation any number of (possibly zero) times:

• Choose an integer i such that 1 \leq i \leq 8 and s_i= 1. Let (x, y) be the current coordinates where the piece is placed.
  • If i=1, move the piece to (x+1,y).
  • If i=2, move the piece to (x+1,y+1).
  • If i=3, move the piece to (x,y+1).
  • If i=4, move the piece to (x-1,y+1).
  • If i=5, move the piece to (x-1,y).
  • If i=6, move the piece to (x-1,y-1).
  • If i=7, move the piece to (x,y-1).
  • If i=8, move the piece to (x+1,y-1).

Your objective is to move the piece to (A, B).
Find the minimum number of operations needed to achieve the objective. If it is impossible, print -1 instead.

Constraints

• 1 \leq T \leq 10^4
• -10^9 \leq A,B \leq 10^9
• s_i is 0 or 1.
• T, A, and B are integers.

Sample Input 1

7
5 3 10101010
5 3 01010101
5 3 11111111
5 3 00000000
0 0 11111111
0 1 10001111
-1000000000 1000000000 10010011

Sample Output 1

8
5
5
-1
0
-1
1000000000