Problem Statement

The following five days are called the five seasonal festivals (gosekku).

• January \color{red}{\mathbf{7}}
• March 3
• May 5
• July 7
• September 9

If month M, day D is one of the five seasonal festivals, output Yes; otherwise, output No.

Constraints

• M and D are integers.
• Month M, day D is a valid date in a leap year in the Gregorian calendar.

Sample Input 1

3 3

Sample Output 1

Yes

March 3 is one of the five seasonal festivals, so output Yes.

Sample Input 2

1 1

Sample Output 2

No

January 1 is not one of the five seasonal festivals, so output No.

Sample Input 3

4 4

Sample Output 3

No

Sample Input 4

11 7

Sample Output 4

No

Problem Statement

You are given positive integers N and M.

If the following operation is repeated while the value of M is not 0, find the number of operations performed.

• Let x be the remainder when N is divided by M. Replace the value of M with x.

It can be proved that M becomes 0 after a finite number of operations.

Constraints

• 1 \leq N, M \leq 1000
• All input values are integers.

Sample Input 1

8 5

Sample Output 1

3

Initially, N = 8 and M = 5.

The remainder when 8 is divided by 5 is 3, so M = 3 after one operation.

The remainder when 8 is divided by 3 is 2, so M = 2 after two operations.

The remainder when 8 is divided by 2 is 0, so M = 0 after three operations.

Thus, output 3 as the answer.

Sample Input 2

14 6

Sample Output 2

2

Sample Input 3

460 33

Sample Output 3

5

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

Problem Statement

You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:

• for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.

Constraints

• 1 \leq N \leq 100
• Each element of A and B is 0 or 1.
• All values in the input are integers.

Sample Input 1

3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1

Sample Output 1

Yes

Initially, A is :

0 1 1
1 0 0
0 1 0

After performing the operation once, A is :

0 1 0
1 0 1 
0 0 1

After performing the operation once again, A is :

0 1 0
0 0 1
1 1 0

Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.

Sample Input 2

2
0 0
0 0
1 1
1 1

Sample Output 2

Yes

Sample Input 3

5
0 0 1 1 0
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
0 0 1 1 1
1 0 1 0 1
1 1 0 1 0

Sample Output 3

No

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

...#.
#.#..
.#...
#.#..
...#.

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

Note that the input may not fit into a 32-bit integer type.

Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388

Problem Statement

Let N be a positive integer. Define the imbalance of a sequence A=(A_1, A_2, \dots, A_{2^N}) of non-negative integers of length 2^N as the non-negative integer value obtained by the following operation:

• Initially, set X=0.
• Perform the following series of operations N times:
  • Update X to \max(X, \max(A) - \min(A)), where \max(A) and \min(A) denote the maximum and minimum values of sequence A, respectively.
  • Form a new sequence of half the length by pairing elements from the beginning two by two and arranging their sums. That is, set A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert}).
• The final value of X is the imbalance.

For example, when N=2, A=(6, 8, 3, 5), the imbalance is 6 through the following steps:

• Initially, X=0.
• The first series of operations is as follows:
  • Update X to \max(X, \max(A) - \min(A)) = \max(0, 8 - 3) = 5.
  • Set A to (6+8, 3+5) = (14, 8).
• The second series of operations is as follows:
  • Update X to \max(X, \max(A) - \min(A)) = \max(5, 14 - 8) = 6.
  • Set A to (14 + 8) = (22).
• Finally, X=6.

You are given a non-negative integer K. Among all sequences of non-negative integers of length 2^N with sum K, construct a sequence that minimizes the imbalance.

Constraints

• 1 \leq N \leq 20
• 0 \leq K \leq 10^9
• N and K are integers.

Sample Input 1

1 11

Sample Output 1

1
5 6

(5, 6) is a sequence with imbalance 1, which is the minimum imbalance among sequences satisfying the condition.

Sample Input 2

3 56

Sample Output 2

0
7 7 7 7 7 7 7 7

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Determine whether it is possible to make S identical to T by repeating the operation below any number of times (possibly zero). If it is possible, also find the minimum number of operations required.

• Choose two lowercase English letters x, y and replace every occurrence of x in S with y.

Constraints

• 1\leq N \leq 2\times 10^5
• N is an integer.
• Each of S and T is a string of length N, consisting of lowercase English letters.

Sample Input 1

6
afbfda
bkckbb

Sample Output 1

4

By performing the operation four times in the following way, you can make S identical to T:

1. Choose x= b and y= c. S becomes afcfda.
2. Choose x= a and y= b. S becomes bfcfdb.
3. Choose x= f and y= k. S becomes bkckdb.
4. Choose x= d and y= b. S becomes bkckbb, which is identical to T.

It cannot be done with fewer than four operations, so the minimum number of operations required is 4.

Sample Input 2

4
abac
abac

Sample Output 2

0

S and T are already identical, so no operations are required.

Sample Input 3

4
abac
abrc

Sample Output 3

-1

No matter how you repeat the operation, it is impossible to make S identical to T.

Sample Input 4

4
abac
bcba

Sample Output 4

4

Problem Statement

For a string S of length N and an integer i\ (0\leq i\leq N), let us define the string f_i(S) as the concatenation of:

• the first i characters of S,
• the reversal of S, and
• the last (N-i) characters of S,

in this order. For instance, if S= abc and i=2, we have f_i(S)= abcbac.

You are given a string T of length 2N. Find a pair of a string S of length N and an integer i\ (0\leq i\leq N) such that f_i(S)=T. If no such pair of S and i exists, report that fact.

Constraints

• 1\leq N \leq 10^6
• N is an integer.
• T is a string of length 2N consisting of lowercase English letters.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if S= abc and i=2, we have f_i(S)= abcbac, which equals T, so you should print abc and 2.

Sample Input 2

4
abababab

Sample Output 2

abab
1

S= abab and i=3 also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

S= agc and i=3 also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of S and i satisfies the condition, print -1.