Problem Statement

You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).

Print all even numbers in A without changing the order.

Constraints

• 1\leq N\leq 100
• 1\leq A _ i\leq 100\ (1\leq i\leq N)
• A contains at least one even number.
• All values in the input are integers.

Sample Input 1

5
1 2 3 5 6

Sample Output 1

2 6

We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.

Sample Input 2

5
2 2 2 3 3

Sample Output 2

2 2 2

A may contain equal elements.

Sample Input 3

10
22 3 17 8 30 15 12 14 11 17

Sample Output 3

22 8 30 12 14

Problem Statement

You are given a string S of length between 1 and 25 consisting of lowercase English letters.
Output one lowercase English letter that does not appear in S.
If there are multiple such letters, you may output any one of them.

Constraints

• S is a string of length between 1 and 25 (inclusive) consisting of lowercase English letters.

Sample Input 1

a

Sample Output 1

d

S= a.
Any lowercase English letter other than a (that is, b, c, …, or z) is a correct answer.

Sample Input 2

abcdfhijklmnopqrstuvwxyz

Sample Output 2

e

The lowercase English letters not included in S are e and g.

Sample Input 3

qazplwsxokmedcijnrfvuhbgt

Sample Output 3

y

Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

• 2 \leq H, W \leq 50
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
2 1 4
3 1 3
6 4 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
• For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

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

You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query (1\le i\le Q) is described as follows:

You are given a character c_i and integers X_i,V_i. If c_i= A, change A_{X_i} to V_i; if c_i= B, change B_{X_i} to V_i. Then, output \displaystyle \sum_{k=1}^N \min(A_k,B_k).

Constraints

• 1\le N,Q \le 2 \times 10^5
• 1\le A_i,B_i \le 10^9
• c_i is either A or B.
• 1\le X_i \le N
• 1\le V_i \le 10^9
• All input values are integers.

Sample Input 1

4 3
3 1 4 1
2 7 1 8
A 2 3
B 3 3
A 1 7

Sample Output 1

7
9
9

After the 1st query, A=(3,3,4,1),B=(2,7,1,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 on the 1st line.

After the 2nd query, A=(3,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 2nd line.

After the 3rd query, A=(7,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 3rd line.

Sample Input 2

1 3
1
1000000000
A 1 1
A 1 1
A 1 1

Sample Output 2

1
1
1

Sample Input 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3

421
420
420

Problem Statement

There are N toys numbered from 1 to N, and N-1 boxes numbered from 1 to N-1. Toy i\ (1 \leq i \leq N) has a size of A_i, and box i\ (1 \leq i \leq N-1) has a size of B_i.

Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:

1. Choose an arbitrary positive integer x and purchase one box of size x.
2. Place each of the N toys into one of the N boxes (the N-1 existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy's size, and no box can contain two or more toys.

He wants to execute step 2 by purchasing a sufficiently large box in step 1, but larger boxes are more expensive, so he wants to purchase the smallest possible box.

Determine whether there exists a value of x such that he can execute step 2, and if it exists, find the minimum such x.

Constraints

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

Sample Input 1

4
5 2 3 7
6 2 8

Sample Output 1

3

Consider the case where x=3 (that is, he purchases a box of size 3 in step 1).

If the newly purchased box is called box 4, toys 1,\dots,4 have sizes of 5, 2, 3, and 7, respectively, and boxes 1,\dots,4 have sizes of 6, 2, 8, and 3, respectively. Thus, toy 1 can be placed in box 1, toy 2 in box 2, toy 3 in box 4, and toy 4 in box 3.

On the other hand, if x \leq 2, it is impossible to place all N toys into separate boxes. Therefore, the answer is 3.

Sample Input 2

4
3 7 2 5
8 1 6

Sample Output 2

-1

No matter what size of box is purchased in step 1, no toy can be placed in box 2, so it is impossible to execute step 2.

Sample Input 3

8
2 28 17 39 57 56 37 32
34 27 73 28 76 61 27

Sample Output 3

37

Problem Statement

AtCoder cafeteria offers N main dishes and M side dishes. The price of the i-th main dish is A_i, and that of the j-th side dish is B_j. The cafeteria is considering introducing a new set meal menu. A set meal consists of one main dish and one side dish. Let s be the sum of the prices of the main dish and the side dish, then the price of the set meal is \min(s,P). Here, P is a constant given in the input.

There are NM ways to choose a main dish and a side dish for a set meal. Find the total price of all these set meals.

Constraints

• 1\leq N,M \leq 2\times 10^5
• 1\leq A_i,B_j \leq 10^8
• 1\leq P \leq 2\times 10^8
• All input values are integers.

Sample Input 1

2 2 7
3 5
6 1

Sample Output 1

24

• If you choose the first main dish and the first side dish, the price of the set meal is \min(3+6,7)=7.
• If you choose the first main dish and the second side dish, the price of the set meal is \min(3+1,7)=4.
• If you choose the second main dish and the first side dish, the price of the set meal is \min(5+6,7)=7.
• If you choose the second main dish and the second side dish, the price of the set meal is \min(5+1,7)=6.

Thus, the answer is 7+4+7+6=24.

Sample Input 2

1 3 2
1
1 1 1

Sample Output 2

6

Sample Input 3

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

Sample Output 3

2115597124

Problem Statement

You are given a string S of length N consisting of three kinds of characters: A, B, and C.

There are \dfrac{N(N+1)}2 non-empty contiguous substrings of S. Find how many of them contain more As than Bs.

Note that two substrings are counted separately if they are taken from different positions in S, even if they are equal as strings.

Constraints

• 1\le N\le5\times10 ^ 5
• S is a string of length N consisting of A, B, and C.
• N is an integer.

Sample Input 1

10
ACBBCABCAB

Sample Output 1

8

The following eight substrings satisfy the condition:

• A: 1st to 1st character of S
• AC: 1st to 2nd character of S
• CA: 5th to 6th character of S
• CABCA: 5th to 9th character of S
• A: 6th to 6th character of S
• ABCA: 6th to 9th character of S
• CA: 8th to 9th character of S
• A: 9th to 9th character of S

All other substrings do not satisfy the condition, so print 8.

Note that A and CA can be taken from multiple positions, but they are counted separately if taken from different positions.

Sample Input 2

4
CCBC

Sample Output 2

0

There may be no substrings that satisfy the condition.

Sample Input 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

Sample Output 3

136

Problem Statement

A sequence a=(a_1,a_2,\dots,a_k) of length k is defined to be kadomatsu-like as follows:

• Let x be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} < a_i, and a_i > a_{i+1}.
• Let y be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} > a_i, and a_i < a_{i+1}.
• The sequence a is called kadomatsu-like if and only if x > y.

You are given a permutation P of (1,2,\dots,N).
Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of P that are kadomatsu-like.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• P is a permutation of (1,2,\dots,N).

Sample Input 1

4
1 3 4 2

Sample Output 1

4

Among the subsequences of P, the following four are kadomatsu-like:

• (1,3,4,2)
• (1,3,2)
• (1,4,2)
• (3,4,2)

Sample Input 2

1
1

Sample Output 2

0

Sample Input 3

20
11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3

Sample Output 3

431610

For example, the subsequence a=(10,13,12,5,7,9,20,3) is kadomatsu-like.

• We have a_{i-1} < a_i and a_i > a_{i+1} for i=2,7, so x=2.
• We have a_{i-1} > a_i and a_i < a_{i+1} for i=4, so y=1.
• Since x > y, the subsequence a is kadomatsu-like.