Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

• All values in input are integers.
• 1 \le R \le H \le 10
• 1 \le C \le W \le 10

Sample Input 1

3 4
2 2

Sample Output 1

4

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.

Sample Input 2

3 4
1 3

Sample Output 2

3

Sample Input 3

3 4
3 4

Sample Output 3

2

When H=3 and W=4, the grid looks as follows.

• For Sample Input 1, there are 4 squares adjacent to Square (2,2).
• For Sample Input 2, there are 3 squares adjacent to Square (1,3).
• For Sample Input 3, there are 2 squares adjacent to Square (3,4).

Sample Input 4

1 10
1 5

Sample Output 4

2

Sample Input 5

8 1
8 1

Sample Output 5

1

Sample Input 6

1 1
1 1

Sample Output 6

0

Problem Statement

Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.

If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?

Constraints

• B and G are different integers between 1 and 1000, inclusive.

Sample Input 1

300 100

Sample Output 1

Bat

The bat is more expensive than the glove, so Santa will give Takahashi the bat.

Sample Input 2

334 343

Sample Output 2

Glove

The glove is more expensive than the bat, so Santa will give Takahashi the glove.

Problem Statement

Given an integer X between -10^{18} and 10^{18} (inclusive), print \left\lfloor \dfrac{X}{10} \right\rfloor.

Notes

For a real number x, \left\lfloor x \right\rfloor denotes "the maximum integer not exceeding x". For example, we have \left\lfloor 4.7 \right\rfloor = 4, \left\lfloor -2.4 \right\rfloor = -3, and \left\lfloor 5 \right\rfloor = 5. (For more details, please refer to the description in the Sample Input and Output.)

Constraints

• -10^{18} \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

47

Sample Output 1

4

The integers that do not exceed \frac{47}{10} = 4.7 are all the negative integers, 0, 1, 2, 3, and 4. The maximum integer among them is 4, so we have \left\lfloor \frac{47}{10} \right\rfloor = 4.

Sample Input 2

-24

Sample Output 2

-3

Since the maximum integer not exceeding \frac{-24}{10} = -2.4 is -3, we have \left\lfloor \frac{-24}{10} \right\rfloor = -3.
Note that -2 does not satisfy the condition, as -2 exceeds -2.4.

Sample Input 3

50

Sample Output 3

5

The maximum integer that does not exceed \frac{50}{10} = 5 is 5 itself. Thus, we have \left\lfloor \frac{50}{10} \right\rfloor = 5.

Sample Input 4

-30

Sample Output 4

-3

Just like the previous example, \left\lfloor \frac{-30}{10} \right\rfloor = -3.

Sample Input 5

987654321987654321

Sample Output 5

98765432198765432

The answer is 98765432198765432. Make sure that all the digits match.

If your program does not behave as intended, we recommend you checking the specification of the programming language you use.
If you want to check how your code works, you may use "Custom Test" above the Problem Statement.

Problem Statement

There is a rectangular chocolate consisting of H rows and W columns of blocks.

You are given Q queries; process them in order and find the answer to each query. Each query is in one of the following formats:

• Type 1: An integer R is given. Find the number of chocolate blocks in the bottom R rows, then eat them.

• Type 2: An integer C is given. Find the number of chocolate blocks in the rightmost C columns, then eat them.

When the queries are processed in order, the chocolate remains rectangular after each query is processed, and it has at least R + 1 rows immediately before processing a type 1 query and has at least C + 1 columns immediately before processing a type 2 query.

Constraints

• 2 \leq H, W \leq 100
• 1 \leq Q \leq 100
• For type 1 queries, 1 \leq R.
• When the queries are processed in order, the chocolate has at least R + 1 rows immediately before processing a type 1 query.
• For type 2 queries, 1 \leq C.
• When the queries are processed in order, the chocolate has at least C + 1 columns immediately before processing a type 2 query.
• All input values are integers.

Sample Input 1

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

Sample Output 1

28
15
4
4
9

Initially, the chocolate is a rectangle with 7 rows and 9 columns.

For the first query, the number of chocolate blocks in the rightmost 4 columns is 28, so output 28. The chocolate becomes 7 rows and 5 columns.

For the second query, the number of chocolate blocks in the bottom 3 rows is 15, so output 15. The chocolate becomes 4 rows and 5 columns.

For the third query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 4 columns.

For the fourth query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 3 columns.

For the fifth query, the number of chocolate blocks in the bottom 3 rows is 9, so output 9. The chocolate becomes 1 row and 3 columns.

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

• All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

Problem Statement

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

Find how many pairs of integers (i,j)\ (1\le i\lt j\le N) satisfy j-i=A _ i+A _ j.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le A _ i\le2\times10 ^ 5\ (1\le i\le N)
• All input values are integers.

Sample Input 1

9
3 1 4 1 5 9 2 6 5

Sample Output 1

3

For example, when (i,j)=(4,7), we have j-i=7-4=3 and A _ i+A _ j=1+2=3, so j-i=A _ i+A _ j.

In contrast, when (i,j)=(3,8), we have j-i=8-3=5 and A _ i+A _ j=4+6=10, so j-i\ne A _ i+A _ j.

Only the three pairs (i,j)=(1,9),(2,4),(4,7) satisfy the condition, so output 3.

Sample Input 2

3
123456 123456 123456

Sample Output 2

0

There may be no pairs that satisfy the condition.

Sample Input 3

30
8 3 6 4 9 6 5 6 5 6 3 4 7 3 7 4 9 8 5 8 3 6 8 8 4 5 5 5 6 5

Sample Output 3

17

Problem Statement

2N people numbered 1, 2, \ldots, 2N attend a ball. They will group into N pairs and have a dance.

If Person i and Person j pair up, where i is smaller than j, the affinity of that pair is A_{i, j}.
If the N pairs have the affinity of B_1, B_2, \ldots, B_N, the total fun of the ball is the bitwise XOR of them: B_1 \oplus B_2 \oplus \cdots \oplus B_N.

Print the maximum possible total fun of the ball when the 2N people can freely group into N pairs.

Constraints

• 1 \leq N \leq 8
• 0 \leq A_{i, j} < 2^{30}
• All values in input are integers.

Sample Input 1

2
4 0 1
5 3
2

Sample Output 1

6

Let \lbrace i, j\rbrace denote a pair of Person i and Person j. There are three ways for the four people to group into two pairs, as follows.

• Group into \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace. The total fun of the ball here is A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6.
• Group into \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace. The total fun of the ball here is A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3.
• Group into \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace. The total fun of the ball here is A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4.

Therefore, the maximum possible total fun of the ball is 6.

Sample Input 2

1
5

Sample Output 2

5

There will be just a pair of Person 1 and Person 2, where the total fun of the ball is 5.

Sample Input 3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

Sample Output 3

1073289207

Problem Statement

A box contains N balls, each with an integer between 1 and M-1 written on it. For i = 1, 2, \ldots, N, the integer written on the i-th ball is A_i.

While the box has two or more balls remaining, Takahashi will repeat the following.

• First, choose two balls arbitrarily.
• Then, get a score equal to the remainder when x^y + y^x is divided by M, where x and y are the integers written on the two balls.
• Finally, choose one of the two balls arbitrarily, eat it, and return the other to the box.

Print the maximum possible total score Takahashi will get.

Constraints

• 2 \leq N \leq 500
• 2 \leq M \leq 10^9
• 1 \leq A_i \leq M-1
• All values in the input are integers.

Sample Input 1

4 10
4 2 3 2

Sample Output 1

20

Consider the following scenario. Below, X \bmod Y denotes the remainder when a non-negative integer X is divided by a positive integer Y.

1. Take the first and third balls from the box to score (4^3 + 3^4) \bmod 10 = 5 points. Then, eat the first ball and return the third to the box. Now, the box has the second, third, and fourth balls.
2. Take the third and fourth balls from the box to score (3^2 + 2^3) \bmod 10 = 7 points. Then, eat the third ball and return the fourth to the box. Now, the box has the second and fourth balls.
3. Take the second and fourth balls from the box to score (2^2 + 2^2) \bmod 10 = 8 points. Then, eat the second ball and return the fourth to the box. Now, the box has just the fourth ball.

Here, Takahashi scores a total of 5 + 7 + 8 = 20 points, which is the maximum possible value.

Sample Input 2

20 100
29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8

Sample Output 2

1733

Problem Statement

You are given N strings S _ 1,S _ 2,\ldots,S _ N. S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters, and the strings are pairwise distinct.

Taro the First and Jiro the Second play a word-chain game. In this game, the two players take alternating turns, with Taro the First going first. In each player's turn, the player chooses an integer i\ (1\leq i\leq N), which should satisfy the following two conditions:

• i is different from any integer chosen by the two players so far since the game started;
• the current turn is the first turn of the game, or the last character of S_j equals the first character of S_i, where j is the last integer chosen.

The player who is unable to choose a conforming i loses; the other player wins.

Determine which player will win if the two players play optimally.

Constraints

• 1 \leq N \leq 16
• N is an integer.
• S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters.
• S _ i\neq S _ j\ (1\leq i\lt j\leq N)

Sample Input 1

6
enum
float
if
modint
takahashi
template

Sample Output 1

First

For example, the game progresses as follows. Note that the two players may not be playing optimally in this example.

• Taro the First chooses i=3. S _ i=if.
• Jiro the Second chooses i=2. S _ i=float, and the last character of if equals the first character of float.
• Taro the First chooses i=5. S _ i=takahashi, and the last character of float equals the first character of takahashi.
• Jiro the Second is unable to choose i\neq2,3,5 such that S _ i starts with i, so he loses.

In this case, Taro the First wins.

Sample Input 2

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

Sample Output 2

Second

Sample Input 3

16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs

Sample Output 3

First