Problem Statement

You are given a sequence of integers A = (A_1, A_2, A_3).
Let B = (B_1, B_2, B_3) be any permutation of A.
Determine whether it is possible that B_1 \times B_2 = B_3.

Constraints

• All input values are integers.
• 1 \le A_1, A_2, A_3 \le 100

Sample Input 1

3 15 5

Sample Output 1

Yes

Here, A=(3,15,5). By rearranging it as B=(3,5,15), we can satisfy B_1 \times B_2 = B_3.

Sample Input 2

5 3 2

Sample Output 2

No

No permutation of B satisfies B_1 \times B_2 = B_3.

Problem Statement

Given integers R, C, and a 2 \times 2 matrix A, print A_{R,C}.

Constraints

• All values in input are integers.
• 1 \le R,C \le 2
• 0 \le A_{i,j} \le 100

Sample Input 1

1 2
1 0
0 1

Sample Output 1

0

We have A_{1,2}=0.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

4

We have A_{2,2}=4.

Sample Input 3

2 1
90 80
70 60

Sample Output 3

70

We have A_{2,1}=70.

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

6

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

• 100 \leq N \leq 919
• N is an integer.

Sample Input 1

320

Sample Output 1

326

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.

Sample Input 2

144

Sample Output 2

144

144 is a 326-like number.

Sample Input 3

516

Sample Output 3

600

Problem Statement

Takahashi observed N birds, numbered 1, 2, \dots, N, over M days.
Each of the birds that Takahashi observed has one of N colors, numbered 1, 2, \dots, N, and these birds have an interesting characteristic: their color can change during the observation period.

Bird i had color A_i in observations on or before day D_i - 1, and color B_i in observations on or after day D_i.
Here, if D_i = 1, then the bird's color was B_i from the observation on day 1, and if A_i = B_i, then the bird's color did not change during the observation period.

For each j = 1, 2, \dots, M, find the number of different colors of birds on day j.

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le M \le 3 \times 10^5
• 1 \le A_i, B_i \le N
• 1 \le D_i \le M
• All input values are integers.

Sample Input 1

6 7
1 3 2
2 6 5
5 5 1
3 3 5
4 1 6
6 3 6

Sample Output 1

5
5
3
3
4
4
4

In this input, six birds are observed over seven days.

• On day 1, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
• On day 2, the color of each bird was 1, 2, 5, 3, 6, 6. There are 5 different colors in total.
• On day 3, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
• On day 4, the color of each bird was 2, 2, 5, 5, 6, 6. There are 3 different colors in total.
• On day 5, the color of each bird was 2, 2, 1, 5, 6, 6. There are 4 different colors in total.
• On day 6, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.
• On day 7, the color of each bird was 2, 5, 1, 5, 6, 6. There are 4 different colors in total.

Problem Statement

There are N types of items item 1 through item N. Initially, Takahashi has only item 1.

He has M friends. If he gives item A_i to the i-th friend (1\le i\le M), he will receive item B_i.

Find how many types of items he can obtain, including item 1.

Constraints

• 2\le N\le 3\times 10^5
• 1\le M\le 3\times 10^5
• 1\le A_i,B_i\le N
• A_i \neq B_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

For example, Takahashi can obtain item 4 by acting as follows:

• Give item 1 to the first friend. Receive item 2.
• Give item 2 to the fourth friend. Receive item 4.

He can obtain four types of items: items 1,2,3,4. Thus, output 4.

Sample Input 2

3 2
2 1
3 2

Sample Output 2

1

He can obtain one type of item: item 1.

Sample Input 3

7 8
2 6
2 5
3 6
1 6
1 2
5 6
2 3
3 7

Sample Output 3

6

Problem Statement

Given are a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and a positive integer K.

For each i=K,K+1,\ldots,N, find the following.

• The K-th greatest value among the first i terms of P.

Constraints

• 1 \leq K \leq N \leq 5 \times 10^5
• (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The (K=) 2-nd greatest value among the first 2 terms of P, (P_1,P_2)=(1,2), is 1.
• The (K=) 2-nd greatest value among the first 3 terms of P, (P_1,P_2,P_3)=(1,2,3), is 2.

Sample Input 2

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

Sample Output 2

2
3
3
5
6
7
7

Problem Statement

There are N rabbits numbered 1 to N on a number line. Rabbit i is at coordinate X_i. Multiple rabbits may be at the same coordinate.
Each rabbit has a parameter called jumping power, and rabbit i has jumping power R_i.
Now, all rabbits will jump exactly once. When a rabbit at coordinate x with jumping power r jumps, it moves to coordinate x+r or coordinate x-r.
If you can freely choose which coordinate each rabbit jumps to, find the maximum possible number of distinct coordinates where rabbits are present after all rabbits have jumped.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i \leq 10^9
• 1 \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

3
4 1
2 3
4 5

Sample Output 1

3

If each rabbit moves as shown below, it is possible to achieve 3 as the number of distinct coordinates where rabbits are present after jumping, and this is the maximum possible.

• Rabbit 1 moves to 4 - 1 = 3.
• Rabbit 2 moves to 2 + 3 = 5.
• Rabbit 3 moves to 4 - 5 = -1.

Sample Input 2

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

Sample Output 2

4

If each rabbit moves as shown below, it is possible to achieve 4 as the number of distinct coordinates where rabbits are present after jumping, and this is the maximum possible.

• Rabbit 1 moves to 2 - 1 = 1.
• Rabbit 2 moves to 3 + 2 = 5.
• Rabbit 3 moves to 6 + 1 = 7.
• Rabbit 4 moves to 5 + 2 = 7.
• Rabbit 5 moves to 4 - 3 = 1.
• Rabbit 6 moves to 4 - 1 = 3.

Sample Input 3

10
1000000000 1000000000
1000000000 1
-1000000000 1000000000
-1000000000 1
0 1
2 1
1 2
4 1
3 2
4 3

Sample Output 3

9

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and Q queries. Process the queries in order.

Each query is of one of the following two kinds:

• 1 x c : replace the x-th character of S by the character c.
• 2 l r : let T be the string obtained by sorting the characters of S in ascending order. Print Yes if the string consisting of the l-th through r-th characters of S is a substring of T; print No otherwise.

Constraints

• 1\leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq Q \leq 10^5
• For each query of the first kind, 1 \leq x \leq N.
• For each query of the first kind, c is a lowercase English letter.
• For each query of the second kind, 1 \leq l \leq r \leq N.

Sample Input 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

Sample Output 1

Yes
No
Yes

• In the 1-st query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string abc, consisting of the 1-st through 3-rd characters of S, is a substring of T, so Yes should be printed.
• In the 2-nd query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string bcdcf, consisting of the 2-nd through 6-th characters of S, is not a substring of T, so No should be printed.
• The 3-rd query sets the 5-th character of S to e, making S abcdef.
• In the 4-th query, abcdef is the string T obtained by sorting the characters of S in ascending order. The string bcdef, consisting of the 2-nd through 6-th characters of S, is a substring of T, so Yes should be printed.