Problem Statement

Takahashi decided to make takoyaki (octopus balls) and serve it to Snuke. Takahashi instructed Snuke to raise only his left hand if he wants to eat takoyaki, and only his right hand otherwise.

You are given the information about which hand Snuke is raising as two integers L and R. He is raising his left hand if and only if L = 1, and raising his right hand if and only if R = 1. He might not follow the instructions and could raise both hands or not raise any hand at all.

If Snuke is raising only one hand, print Yes if he wants to eat takoyaki, and No if he does not. If he is raising both hands or not raising any hand, print Invalid.

Assume that if Snuke is raising only one hand, he is always following the instructions.

Constraints

• Each of L and R is 0 or 1.

Sample Input 1

1 0

Sample Output 1

Yes

Snuke wants to eat takoyaki, so he is raising only his left hand.

Sample Input 2

1 1

Sample Output 2

Invalid

Snuke is raising both hands.

Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

• In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
• Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

• 0 \leq M \lt N \leq 100
• 1 \leq X \leq N
• 1 \leq T \leq 200
• 1 \leq D \leq 100
• Takahashi was at least 1 centimeter tall at his birth.
• All values in input are integers.

Sample Input 1

38 20 17 168 3

Sample Output 1

168

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

1

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

90

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

Constraints

• 0 \leq N \leq 21
• N is an integer.

Sample Input 1

3

Sample Output 1

0 0 0
0 0 1
0 0 2
0 0 3
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 3 0
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 2 0
2 0 0
2 0 1
2 1 0
3 0 0

Sample Input 2

4

Sample Output 2

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

Problem Statement

You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

4

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

2

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

• Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
• Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
  • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

• H and W are integers.
• 1 \le H,W
• 1 \le H \times W \le 4 \times 10^5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

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

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

Problem Statement

There are N bags, labeled bag 1, bag 2, \ldots, bag N.
Bag i (1 \leq i \leq N) contains A_i stones.

Takahashi can perform the following operation any number of times, possibly zero:

Choose two bags A and B, and move all stones from bag A into bag B.

Find the number of different possible values for the following after repeating the operation.

• B_1 \oplus B_2 \oplus \cdots \oplus B_N, where B_i is the final number of stones in bag i.
  Here, \oplus denotes bitwise XOR.

It can be proved that under the constraints of this problem, the number of possible values is finite.

Constraints

• 2 \leq N \leq 12
• 1 \leq A_i \leq 10^{17}
• All input values are integers.

Sample Input 1

3
2 5 7

Sample Output 1

3

For example, if Takahashi chooses bags 1 and 3 for the operation, then the numbers of stones in bags 1, 2, 3 become 0, 5, 9.
If he stops at this point, the XOR is 0 \oplus 5 \oplus 9 = 12.

The other possible XOR values after repeating the operation are 0 and 14.
Therefore, the possible values are 0, 12, 14; there are three values, so the output is 3.

Sample Input 2

2
100000000000000000 100000000000000000

Sample Output 2

2

Sample Input 3

6
71 74 45 34 31 60

Sample Output 3

84

Problem Statement

We have a tree with 2^N-1 vertices.
The vertices are numbered 1 through 2^N-1. For each 1\leq i < 2^{N-1}, the following edges exist:

• an undirected edge connecting Vertex i and Vertex 2i,
• an undirected edge connecting Vertex i and Vertex 2i+1.

There is no other edge.

Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.

Find the number, modulo 998244353, of pairs of vertices (i, j) such that the distance between them is D.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq D \leq 2\times 10^6
• All values in input are integers.

Sample Input 1

3 2

Sample Output 1

14

The following figure describes the given tree.

There are 14 pairs of vertices such that the distance between them is 2: (1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6).

Sample Input 2

14142 17320

Sample Output 2

11284501

Problem Statement

You are given an integer N. Print a string S that satisfies all of the following conditions. If no such string exists, print -1.

• S is a string of length between 1 and 1000, inclusive, consisting of the characters 1, 2, 3, 4, 5, 6, 7, 8, 9, and * (multiplication symbol).
• S is a palindrome.
• The first character of S is a digit.
• The value of S when evaluated as a formula equals N.

Constraints

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

Sample Input 1

363

Sample Output 1

11*3*11

S = 11*3*11 satisfies the conditions in the problem statement. Another string that satisfies the conditions is S= 363.

Sample Input 2

101

Sample Output 2

-1

Note that S must not contain the digit 0.

Sample Input 3

3154625100

Sample Output 3

2*57*184481*75*2