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

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

• 1000 \leq y \leq 9000
• 1 \leq m \leq M \leq 99
• 1 \leq d \leq D \leq 99
• All input values are integers.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

• 1 \leq N \leq 2000
• 0 \leq A_i \leq 2000
• All values in input are integers.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

• choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

• Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
• S and T have the same length.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

• N is an integer.
• 1 \leq N \leq 16

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

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

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

You are given integers N and K, along with N integer sequences A_1, A_2, \ldots, A_N and a length-N integer sequence C = (C_1, C_2, \ldots, C_N). The length of integer sequence A_i is L_i, and A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i}). It is guaranteed that \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i.

Construct an integer sequence B = (B_1, B_2, \ldots, B_{\sum_{i=1}^N C_iL_i}) from A and C using the following procedure.

• Let B be an integer sequence of length 0.
• For i = 1, 2, \ldots, N in this order, perform the following operation:
  • Do this C_i times: append A_i to the end of B.

Find the value of B_K.

Constraints

• 1 \le N
• 1 \le L_i
• \displaystyle \sum_{i=1}^N L_i \le 2 \times 10^5
• 1 \le A_{i,j} \le 10^9 (1 \le j \le L_i)
• 1 \le C_i \le 10^9
• \displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

B is constructed as follows:

• Let B = ().
• Append A_1 to the end of B once. We get B = (1, 3, 2).
• Append A_2 to the end of B three times. We get B = (1, 3, 2, 3, 3, 3).
• Append A_3 to the end of B twice. We get B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3).

For B = (1, 3, 2, 3, 3, 3, 4, 3, 4, 3), we have B_9 = 4, so output 4.

Sample Input 2

3 1
1 7
1 111
1 5
1 100 10000

Sample Output 2

7

Sample Input 3

3 3163812
5 1 2 3 4 5
4 9 8 7 6
2 10 11
87043 908415 9814

Sample Output 3

9

Problem Statement

There is a grid with H rows and W columns. We call the cell at the i-th row from the top (1\leq i\leq H) and j-th column from the left (1\leq j\leq W) as cell (i,j).

Initially, cell (i,j) is colored black if S_{i,j} is # and white if it is ..

Perform the following operation 10^{100} times:

• Let T be the set of cells that are colored white and have exactly one adjacent cell colored black. Color each cell in T black. Here, two cells (i_1,j_1) and (i_2,j_2) are adjacent if and only if |i_1-i_2|+|j_1-j_2|=1.

Find the number of cells that are colored black after all operations are completed.

Constraints

• 2\leq H,W
• HW\leq 3\times 10^5
• H and W are integers.
• S_{i,j} is # or ..

Sample Input 1

9 9
.........
.........
.........
.........
....#....
.........
.........
.........
.........

Sample Output 1

57

The grid changes as follows through the operations. (The number above represents the operation count. The first ten operations are displayed.)

Eventually, 57 cells are colored black.

Sample Input 2

2 2
..
..

Sample Output 2

0

Sample Input 3

10 10
..........
....#.....
#.......#.
......#...
.......#..
.....#....
..........
..........
..#...#...
.......#..

Sample Output 3

64

Problem Statement

For a binary string B = B_1 B_2 \dots B_{3^n} of length 3^n (n \geq 1), we define an operation to obtain a binary string C = C_1 C_2 \dots C_{3^{n-1}} of length 3^{n-1} as follows:

• Partition the elements of B into groups of 3 and take the majority value from each group. That is, for i=1,2,\dots,3^{n-1}, let C_i be the value that appears most frequently among B_{3i-2}, B_{3i-1}, and B_{3i}.

You are given a binary string A = A_1 A_2 \dots A_{3^N} of length 3^N. Let A' = A'_1 be the length-1 string obtained by applying the above operation N times to A.

Determine the minimum number of elements of A that must be changed (from 0 to 1 or from 1 to 0) in order to change the value of A'_1.

Constraints

• N is an integer with 1 \leq N \leq 13.
• A is a string of length 3^N consisting of 0 and 1.

Sample Input 1

2
010011101

Sample Output 1

1

For example, with A=010011101, after applying the operation twice, we obtain:

• First operation: The majority of 010 is 0, of 011 is 1, and of 101 is 1, resulting in 011.
• Second operation: The majority of 011 is 1, yielding 1.

To change the final value from 1 to 0, one way is to change the 5th character of A from 1 to 0, yielding A=010001101. After the change, the operations yield:

• First operation: The majority of 010 is 0, of 001 is 0, and of 101 is 1, resulting in 001.
• Second operation: The majority of 001 is 0, yielding 0.

Thus, the minimum number of changes required is 1.

Sample Input 2

1
000

Sample Output 2

2

Problem Statement

For a string X of length n, let f(X,k) denote the string obtained by repeating k times the string X, and g(X,k) denote the string obtained by repeating k times the first character, the second character, \dots, the n-th character of X, in this order. For example, if X= abc, then f(X,2)= abcabc, and g(X,3)= aaabbbccc. Also, for any string X, both f(X,0) and g(X,0) are empty strings.

You are given a positive integer N and strings S and T. Find the largest non-negative integer k such that g(T,k) is a (not necessarily contiguous) subsequence of f(S,N). Note that g(T,0) is always a subsequence of f(S,N) by definition.

Constraints

• N is an integer.
• 1\leq N\leq 10^{12}
• S and T are strings consisting of lowercase English letters with lengths between 1 and 10^5, inclusive.

Sample Input 1

3
abc
ab

Sample Output 1

2

We have f(S,3)= abcabcabc. g(T,2)= aabb is a subsequence of f(S,3), but g(T,3)= aaabbb is not, so print 2.

Sample Input 2

3
abc
arc

Sample Output 2

0

Sample Input 3

1000000000000
kzazkakxkk
azakxk

Sample Output 3

344827586207