Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

• 0 \leq A \leq 9
• 0 \leq B \leq 9
• A + B \leq 9
• A and B are integers.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

• 2 \leq N \leq 100
• A_{i,j} \in \lbrace 0,1 \rbrace
• A_{i,i} = 0
• A_{i,j} = A_{j,i}
• All input values are integers.

Sample Input 1

4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

Sample Output 1

2 3
1 4
1
2

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

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

Sample Output 3

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

Problem Statement

You are given a positive integer N.

Find the maximum value of a palindromic cube number not greater than N.

Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:

• There is a positive integer x such that x^3 = K.
• The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.

Constraints

• N is a positive integer not greater than 10^{18}.

Sample Input 1

345

Sample Output 1

343

343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.

Sample Input 2

6

Sample Output 2

1

Sample Input 3

123456789012345

Sample Output 3

1334996994331

Problem Statement

Takahashi is hosting a contest with N players numbered 1 to N. The players will compete for points. Currently, all players have zero points.

Takahashi's foreseeing ability lets him know how the players' scores will change. Specifically, for i=1,2,\dots,T, the score of player A_i will increase by B_i points at i seconds from now. There will be no other change in the scores.

Takahashi, who prefers diversity in scores, wants to know how many different score values will appear among the players' scores at each moment. For each i=1,2,\dots,T, find the number of different score values among the players' scores at i+0.5 seconds from now.

For example, if the players have 10, 20, 30, and 20 points at some moment, there are three different score values among the players' scores at that moment.

Constraints

• 1\leq N, T\leq 2\times 10^5
• 1\leq A_i \leq N
• 1\leq B_i \leq 10^9
• All input values are integers.

Sample Input 1

3 4
1 10
3 20
2 10
2 10

Sample Output 1

2
3
2
2

Let S be the sequence of scores of players 1, 2, 3 in this order. Currently, S=\lbrace 0,0,0\rbrace.

• After one second, the score of player 1 increases by 10 points, making S=\lbrace 10,0,0\rbrace. Thus, there are two different score values among the players' scores at 1.5 seconds from now.
• After two seconds, the score of player 3 increases by 20 points, making S=\lbrace 10,0,20\rbrace. Thus, there are three different score values among the players' scores at 2.5 seconds from now.
• After three seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,10,20\rbrace. Therefore, there are two different score values among the players' scores at 3.5 seconds from now.
• After four seconds, the score of player 2 increases by 10 points, making S=\lbrace 10,20,20\rbrace. Therefore, there are two different score values among the players' scores at 4.5 seconds from now.

Sample Input 2

1 3
1 3
1 4
1 3

Sample Output 2

1
1
1

Sample Input 3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

Sample Output 3

2
2
3
3
4
4
5
5
6
5

Problem Statement

In a coordinate space, we want to place three cubes with a side length of 7 so that the volumes of the regions contained in exactly one, two, three cube(s) are V_1, V_2, V_3, respectively.

For three integers a, b, c, let C(a,b,c) denote the cubic region represented by (a\leq x\leq a+7) \land (b\leq y\leq b+7) \land (c\leq z\leq c+7).

Determine whether there are nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 that satisfy all of the following conditions, and find one such tuple if it exists.

• |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| \leq 100
• Let C_i = C(a_i, b_i, c_i)\ (i=1,2,3).
  • The volume of the region contained in exactly one of C_1, C_2, C_3 is V_1.
  • The volume of the region contained in exactly two of C_1, C_2, C_3 is V_2.
  • The volume of the region contained in all of C_1, C_2, C_3 is V_3.

Constraints

• 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3
• All input values are integers.

Sample Input 1

840 84 7

Sample Output 1

Yes
0 0 0 0 6 0 6 0 0

Consider the case (a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (0, 0, 0, 0, 6, 0, 6, 0, 0).

The figure represents the positional relationship of C_1, C_2, and C_3, corresponding to the orange, cyan, and green cubes, respectively.

Here,

• All of |a_1|, |b_1|, |c_1|, |a_2|, |b_2|, |c_2|, |a_3|, |b_3|, |c_3| are not greater than 100.
• The region contained in all of C_1, C_2, C_3 is (6\leq x\leq 7)\land (6\leq y\leq 7) \land (0\leq z\leq 7), with a volume of (7-6)\times(7-6)\times(7-0)=7.
• The region contained in exactly two of C_1, C_2, C_3 is ((0\leq x < 6)\land (6\leq y\leq 7) \land (0\leq z\leq 7))\lor((6\leq x\leq 7)\land (0\leq y < 6) \land (0\leq z\leq 7)), with a volume of (6-0)\times(7-6)\times(7-0)\times 2=84.
• The region contained in exactly one of C_1, C_2, C_3 has a volume of 840.

Thus, all conditions are satisfied.

(a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3) = (-10, 0, 0, -10, 0, 6, -10, 6, 1) also satisfies all conditions and would be a valid output.

Sample Input 2

343 34 3

Sample Output 2

No

No nine integers a_1, b_1, c_1, a_2, b_2, c_2, a_3, b_3, c_3 satisfy all of the conditions.

Problem Statement

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

Process Q queries in the order they are given. Each query is of one of the following two types:

• Type 1: Given in the form 1 p x. Change the value of A_p to x.
• Type 2: Given in the form 2 l r. print the number of occurrences of the second largest value in (A_l, A_{l+1}, \ldots, A_r). More precisely, print the number of integers i satisfying l \leq i \leq r such that there is exactly one distinct value greater than A_i among A_l, A_{l+1}, \ldots, A_r.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• For type-1 queries, 1 \leq p \leq N.
• For type-1 queries, 1 \leq x \leq 10^9.
• For type-2 queries, 1 \leq l \leq r \leq N.
• There is at least one type-2 query.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
0
2

Initially, A = (3, 3, 1, 4, 5).

For the first query, the second largest value in (3, 3, 1) is 1, which appears once in 3, 3, 1, so print 1.

For the second query, there is no second largest value in (5), so print 0.

The third query makes A = (3, 3, 3, 4, 5).

For the fourth query, the second largest value in (3, 3, 4), is 3, which appears twice in 3, 3, 4, so print 2.

Sample Input 2

1 1
1000000000
2 1 1

Sample Output 2

0

Sample Input 3

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

Sample Output 3

0
1
0
2
4

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N.

Find the minimum length of a string that contains all these strings as substrings.

Here, a string S contains a string T as a substring if T can be obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.

Constraints

• N is an integer.
• 1 \leq N \leq 20
• S_i is a string consisting of lowercase English letters whose length is at least 1.
• The total length of S_1, S_2, \dots, S_N is at most 2\times 10^5.

Sample Input 1

3
snuke
kensho
uk

Sample Output 1

9

The string snukensho of length 9 contains all of S_1, S_2, and S_3 as substrings.

Specifically, the first to fifth characters of snukensho correspond to S_1, the fourth to ninth correspond to S_2, and the third to fourth correspond to S_3.

No shorter string contains all of S_1, S_2, and S_3 as substrings. Thus, the answer is 9.

Sample Input 2

3
abc
abc
arc

Sample Output 2

6

Sample Input 3

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

Sample Output 3

27