Problem Statement

You are given a string S consisting of uppercase English letters. Here, the length of S is odd.

Print the string obtained by deleting the middle character of S. The middle character of S is the \frac{L+1}{2}-th character of S, where L is the length of S.

Constraints

• S is a string consisting of uppercase English letters.
• The length of S is an odd number between 3 and 9, inclusive.

Sample Input 1

ABCDE

Sample Output 1

ABDE

The middle character of ABCDE is the 3-rd character C, so print ABDE.

Sample Input 2

OOO

Sample Output 2

OO

Sample Input 3

ATCODER

Sample Output 3

ATCDER

Problem Statement

For a positive integer x, define f(x) as the sum of the digits in the decimal representation of x. For example, f(123) = 1 + 2 + 3 = 6.

Define an infinite sequence A = (A_0, A_1, A_2, \ldots) by the following formula:

• A_0 = 1
• For i \geq 1, A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

You are given a positive integer N. Find the value of A_N.

Constraints

• N is an integer between 1 and 100, inclusive.

Sample Input 1

6

Sample Output 1

23

• A_0 = 1
• A_1 = f(A_0) = 1
• A_2 = f(A_0) + f(A_1) = 2
• A_3 = f(A_0) + f(A_1) + f(A_2) = 4
• A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
• A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
• A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

Thus, A_6 = 23.

Sample Input 2

45

Sample Output 2

427

Problem Statement

There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

You will perform the following operation zero or more times:

• Choose one edge that has not been deleted yet, and delete it.

Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.

Constraints

• 2\le N\le10
• 1\le M\le\dfrac{N(N-1)}2
• 1\le u _ i\lt v _ i\le N\ (1\le i\le M)
• The given graph is simple.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.

It is impossible to make the graph bipartite by performing one or less operations, so print 2.

Sample Input 2

2 1
1 2

Sample Output 2

0

The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.

Sample Input 3

10 20
5 9
1 4
3 8
1 6
4 10
5 7
5 6
3 7
3 6
5 10
1 3
3 4
6 7
1 2
4 7
1 5
1 9
9 10
4 5
8 9

Sample Output 3

5

Problem Statement

There is a directed graph with N vertices and M edges. The vertices are numbered from 1 to N, and the i-th edge is a directed edge from vertex U_i to vertex V_i. Here, the out-degree of each vertex is at least 1.

Also, each vertex has a character written on it, and the character written on vertex i is S_i. Here, S_i refers to the i-th character of S.

Alice and Bob play the following game on this graph using one piece:

• Initially, the piece is placed on vertex 1, and they alternately perform the following operation K times each, with Alice going first and Bob going second.

  • Let u be the vertex where the piece is currently placed. Choose a vertex v such that there is an edge from vertex u to vertex v, and move the piece to vertex v.

• Let v be the vertex where the piece is finally placed. If S_v = A, Alice wins; if S_v = B, Bob wins.

Find the winner of the game when both players play optimally.

In each input, you are given T test cases. Solve each of them.

Constraints

• 1 \leq T
• 2 \leq N, M \leq 2 \times 10^5
• 1 \leq K \leq 10
• S is a string of length N consisting of A and B.
• 1 \leq U_i, V_i \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j .
• The out-degree of each vertex is at least 1.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.
• The sum of M over all test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
4 6 2
AABB
1 2
2 3
3 1
3 3
3 4
4 2
4 6 2
ABAB
1 2
2 3
3 1
3 3
3 4
4 2
5 8 3
ABABB
1 2
2 2
2 3
3 1
3 4
4 4
4 5
5 3

Sample Output 1

Alice
Bob
Bob

We will explain an example of how the game proceeds in the first test case. Here, both players do not necessarily play optimally.

• Initially, the piece is placed on vertex 1.
• Alice moves the piece to vertex 2.
• Bob moves the piece to vertex 3.
• Alice moves the piece to vertex 3.
• Bob moves the piece to vertex 1.

At this point, S_1 = A, so Alice wins.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Takahashi is on one of the cells in this grid, and there is trash on some cells of the grid.

The states of the cells are given by H strings S_1, S_2, \ldots, S_H of length W, where S_{i, j} denotes the j-th character of S_i and represents the following state:

• If S_{i, j} = T, cell (i, j) is the cell where Takahashi is.
• If S_{i, j} = #, cell (i, j) is a cell with trash.
• If S_{i, j} = ., cell (i, j) is an empty cell without trash.

There is no trash on the cell where Takahashi is.

He can repeatedly perform the following operation:

• Choose one of the four directions (up, down, left, or right), and move all trash simultaneously one cell in that direction. Here, if trash goes outside the grid, the trash disappears, and if trash moves to the cell where he is, he gets dirty.

Determine whether it is possible for him to make all trash disappear without getting dirty, and if possible, find the minimum possible number of operations.

Constraints

• 2 \leq H, W \leq 12
• S_i is a string of length W consisting of T, #, and ..
• There is exactly one (i, j) such that S_{i, j} = T.
• There is at least one (i, j) such that S_{i, j} = #.

Sample Input 1

3 4
###.
#.T.
...#

Sample Output 1

3

Takahashi can make all trash disappear in three operations as follows:

• Choose up. After this operation, trash is on cells (1, 1) and (2, 4).

• Choose right. After this operation, trash is on cell (1, 2).

• Choose up. After this operation, all trash has disappeared.

Sample Input 2

3 3
###
#T#
###

Sample Output 2

-1

Sample Input 3

5 5
###..
#T...
..##.
##..#
#..#.

Sample Output 3

5

Problem Statement

You are given a length-N integer sequence A=(A _ 1,A _ 2,\ldots,A _ N).

There are 2 ^ N (not necessarily contiguous) subsequences of A. Find how many subsequences (A _ {i _ 1},A _ {i _ 2},\ldots,A _ {i _ k})\ (1\le i _ 1\lt i _ 2\lt\cdots\lt i _ k\le N) satisfy both of the following two conditions:

• The selected elements are not adjacent in A. That is, 1+i _ j\ne i _ {j+1} holds for all 1\le j\lt k.
• The sum is a multiple of M. That is, \displaystyle\sum _ {j=1} ^ kA _ {i _ j}\equiv0\pmod M.

Even if two subsequences are equal as integer sequences, they are counted separately if the positions from which they are taken are different.

Constraints

• 1\le N\le60
• 1\le M\le10 ^ 9
• 0\le A _ i\lt M
• All input values are integers.

Sample Input 1

7 6
3 1 4 1 5 3 2

Sample Output 1

6

The following six subsequences satisfy the conditions:

• ()=()
• (A _ 1,A _ 3,A _ 5)=(3,4,5)
• (A _ 1,A _ 4,A _ 7)=(3,1,2)
• (A _ 1,A _ 6)=(3,3)
• (A _ 2,A _ 5)=(1,5)
• (A _ 3,A _ 7)=(4,2)

Thus, print 6.

Sample Input 2

15 10
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

Sample Output 2

798

Sample Input 3

20 998244353
778718481 719092922 676292280 713825156 0 434453766 620370916 67922064 0 577696866 21516423 955580612 955580612 0 332156721 0 0 0 632133714 500614291

Sample Output 3

40

Problem Statement

Takahashi will receive some presents from now on.

He has an integer parameter called mood, and the mood changes each time he receives a present. Each present has an integer parameter called value P, and Takahashi's mood changes according to this parameter as follows:

• If the value P of the received present is greater than or equal to the mood value, he is delighted with the present, and the mood increases by A.
• If the value P of the received present is less than the mood value, he is disappointed with the present, and the mood decreases by B.

Initially, there are N presents that Takahashi is scheduled to receive, and the value of the i-th present he will receive (1\le i\le N) is P _ i.

You are given Q queries consisting of two types: addition queries and question queries. Process all of them in order, and answer all question queries.

The i-th query is represented by two integers T _ i,X _ i, and it is an addition query if T _ i=1, and a question query if T _ i=2.

In an addition query, add a new present with value X _ i to the end of the presents to be received.

In a question query, answer the following question:

Find Takahashi's mood after receiving all the presents he is scheduled to receive when his mood is initially X _ i.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le A\le10 ^ 9
• 1\le B\le10 ^ 9
• -10 ^ 9\le P _ i\le10 ^ 9\ (1\le i\le N)
• 1\le Q\le2\times10 ^ 5
• T _ i=1 or T _ i=2\ (1\le i\le Q)
• There exists an integer i\ (1\le i\le Q) such that T _ i=2.
• If T _ i=1, then -10 ^ 9\le X _ i\le10 ^ 9. (1\le i\le Q)
• If T _ i=2, then -10 ^ {12}\le X _ i\le10 ^ {12}. (1\le i\le Q)
• All input values are integers.

Sample Input 1

4 31 41
59 -26 53 58
5
2 9
1 79
2 32
1 38
2 462

Sample Output 1

61
43
216

Initially, the values of the presents Takahashi is scheduled to receive are 59,-26,53,58, in the order he will receive them.

The five queries are as follows:

• When his mood is initially 9, his mood changes as 9\rightarrow40\rightarrow-1\rightarrow30\rightarrow61 each time he receives a present, so print the final mood 61.
• A present with value 79 is added to the presents he is scheduled to receive, and the values of the presents he is scheduled to receive become 59,-26,53,58,79.
• When his mood is initially 32, his mood changes as 32\rightarrow63\rightarrow22\rightarrow53\rightarrow84\rightarrow43 each time he receives a present, so print the final mood 43.
• A present with value 38 is added to the presents he is scheduled to receive, and the values of the presents he is scheduled to receive become 59,-26,53,58,79,38.
• When his mood is initially 462, his mood changes as 462\rightarrow421\rightarrow380\rightarrow339\rightarrow298\rightarrow257\rightarrow216 each time he receives a present, so print the final mood 216.

Sample Input 2

3 1000000000 1000000000
1000000000 0 -1000000000
3
2 -1000000000000
2 0
2 1000000000000

Sample Output 2

-997000000000
-1000000000
997000000000

Note that the absolute value of the input and the values to be output may be 2 ^ {32} or greater.

Sample Input 3

20 8489 1428
6312 -9511 1048 -5301 -2588 -7097 -3342 5209 7493 3378 -5300 6592 7862 -8118 8109 1116 5549 3953 9244 7773
10
1 1694
2 -9723
2 -5195
2 -1384
1 1149
2 9845
2 -7720
2 8329
2 -4652
2 -5672

Sample Output 3

9874
14402
8296
8180
10449
6664
3600
12497