Problem Statement

Print the K-th element of the following sequence of length 32:

1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51

Constraints

• 1 \leq K \leq 32
• All values in input are integers.

Sample Input 1

6

Sample Output 1

2

The 6-th element is 2.

Sample Input 2

27

Sample Output 2

5

The 27-th element is 5.

Problem Statement

We have a board with H horizontal rows and W vertical columns of squares. There is a bishop at the top-left square on this board. How many squares can this bishop reach by zero or more movements?

Here the bishop can only move diagonally. More formally, the bishop can move from the square at the r_1-th row (from the top) and the c_1-th column (from the left) to the square at the r_2-th row and the c_2-th column if and only if exactly one of the following holds:

• r_1 + c_1 = r_2 + c_2
• r_1 - c_1 = r_2 - c_2

For example, in the following figure, the bishop can move to any of the red squares in one move:

Constraints

• 1 \leq H, W \leq 10^9
• All values in input are integers.

Sample Input 1

4 5

Sample Output 1

10

The bishop can reach the cyan squares in the following figure:

Sample Input 2

7 3

Sample Output 2

11

The bishop can reach the cyan squares in the following figure:

Sample Input 3

1000000000 1000000000

Sample Output 3

500000000000000000

Problem Statement

Does \sqrt{a} + \sqrt{b} < \sqrt{c} hold?

Constraints

• 1 \leq a, b, c \leq 10^9
• All values in input are integers.

Sample Input 1

2 3 9

Sample Output 1

No

\sqrt{2} + \sqrt{3} < \sqrt{9} does not hold.

Sample Input 2

2 3 10

Sample Output 2

Yes

\sqrt{2} + \sqrt{3} < \sqrt{10} holds.

Problem Statement

In this problem, we only consider strings consisting of lowercase English letters.

Strings s and t are said to be isomorphic when the following conditions are satisfied:

• |s| = |t| holds.
• For every pair i, j, one of the following holds:
  • s_i = s_j and t_i = t_j.
  • s_i \neq s_j and t_i \neq t_j.

For example, abcac and zyxzx are isomorphic, while abcac and ppppp are not.

A string s is said to be in normal form when the following condition is satisfied:

• For every string t that is isomorphic to s, s \leq t holds. Here \leq denotes lexicographic comparison.

For example, abcac is in normal form, but zyxzx is not since it is isomorphic to abcac, which is lexicographically smaller than zyxzx.

You are given an integer N. Print all strings of length N that are in normal form, in lexicographically ascending order.

Constraints

• 1 \leq N \leq 10
• All values in input are integers.

Sample Input 1

1

Sample Output 1

a

Sample Input 2

2

Sample Output 2

aa
ab

Problem Statement

Snuke has a string s. From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

• Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with ?s.

For example, if s is mississippi, we can choose the substring ssissip and replace its 1-st and 3-rd characters with ? to obtain ?s?ssip.

You are given the strings a, b, and c. Find the minimum possible length of s.

Constraints

• 1 \leq |a|, |b|, |c| \leq 2000
• a, b, and c consists of lowercase English letters and ?s.

Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.

Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.

Problem Statement

For a non-negative integer K, we define a fractal of level K as follows:

• A fractal of level 0 is a grid with just one white square.
• When K > 0, a fractal of level K is a 3^K \times 3^K grid. If we divide this grid into nine 3^{K-1} \times 3^{K-1} subgrids:
  • The central subgrid consists of only black squares.
  • Each of the other eight subgrids is a fractal of level K-1.

For example, a fractal of level 2 is as follows:

In a fractal of level 30, let (r, c) denote the square at the r-th row from the top and the c-th column from the left.

You are given Q quadruples of integers (a_i, b_i, c_i, d_i). For each quadruple, find the distance from (a_i, b_i) to (c_i, d_i).

Here the distance from (a, b) to (c, d) is the minimum integer n that satisfies the following condition:

• There exists a sequence of white squares (x_0, y_0), \ldots, (x_n, y_n) satisfying the following conditions:
  • (x_0, y_0) = (a, b)
  • (x_n, y_n) = (c, d)
  • For every i (0 \leq i \leq n-1), (x_i, y_i) and (x_{i+1}, y_{i+1}) share a side.

Constraints

• 1 \leq Q \leq 10000
• 1 \leq a_i, b_i, c_i, d_i \leq 3^{30}
• (a_i, b_i) \neq (c_i, d_i)
• (a_i, b_i) and (c_i, d_i) are white squares.
• All values in input are integers.

Sample Input 1

2
4 2 7 4
9 9 1 9

Sample Output 1

5
8