Problem Statement

Given eight integers S_1,S_2,\dots, and S_8, print Yes if they satisfy all of the following three conditions, and No otherwise.

• The sequence (S_1,S_2,\dots,S_8) is monotonically non-decreasing. In other words, S_1 \leq S_2 \leq \dots \leq S_8.
• S_1,S_2,\dots, and S_8 are all between 100 and 675, inclusive.
• S_1,S_2,\dots, and S_8 are all multiples of 25.

Constraints

• 0\leq S_i \leq 1000
• All input values are integers.

Sample Input 1

125 175 250 300 400 525 600 650

Sample Output 1

Yes

They satisfy all of the three conditions.

Sample Input 2

100 250 300 400 325 575 625 675

Sample Output 2

No

They violate the first condition because S_4 > S_5.

Sample Input 3

0 23 24 145 301 413 631 632

Sample Output 3

No

They violate the second and third conditions.

Problem Statement

Takahashi ate N plates of sushi at a sushi restaurant. The color of the i-th plate is represented by a string C_i.

The price of a sushi corresponds to the color of the plate. For each i=1,\ldots,M, the sushi on a plate whose color is represented by a string D_i is worth P_i yen a plate (yen is the currency of Japan). If the color does not coincide with any of D_1,\ldots, and D_M, it is worth P_0 yen a plate.

Find the total amount of the prices of sushi that Takahashi ate.

Constraints

• 1\leq N,M\leq 100
• C_i and D_i are strings of length between 1 and 20, inclusive, consisting of lowercase English letters.
• D_1,\ldots, and D_M are distinct.
• 1\leq P_i\leq 10000
• N, M, and P_i are integers.

Sample Input 1

3 2
red green blue
blue red
800 1600 2800

Sample Output 1

5200

A blue plate, red plate, and green plate are worth P_1 = 1600, P_2 = 2800, and P_0 = 800 yen, respectively.

The total amount of the prices of the sushi that he ate is 2800+800+1600=5200 yen.

Sample Input 2

3 2
code queen atcoder
king queen
10 1 1

Sample Output 2

21

Problem Statement

N people numbered 1 through N tossed a coin several times. We know that person i's tosses resulted in A_i heads and B_i tails.

Person i's success rate of the tosses is defined by \displaystyle\frac{A_i}{A_i+B_i}. Sort people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.

Constraints

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

Sample Input 1

3
1 3
3 1
2 2

Sample Output 1

2 3 1

Person 1's success rate is 0.25, person 2's is 0.75, and person 3's is 0.5.

Sort them in descending order of their success rates to obtain the order in Sample Output.

Sample Input 2

2
1 3
2 6

Sample Output 2

1 2

Note that person 1 and 2 should be printed in ascending order of their numbers, as they have the same success rates.

Sample Input 3

4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

Sample Output 3

3 1 4 2

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell at the i-th row from the top and j-th column from the left. Each cell in the grid has a lowercase English letter written on it. The letter written on (i,j) equals the j-th character of a given string S_i.

Snuke will repeat moving to an adjacent cell sharing a side to travel from (1,1) to (H,W). Determine if there is a path in which the letters written on the visited cells (including initial (1,1) and final (H,W)) are s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots, in the order of visiting. Here, a cell (i_1,j_1) is said to be an adjacent cell of (i_2,j_2) sharing a side if and only if |i_1-i_2|+|j_1-j_2| = 1.

Formally, determine if there is a sequence of cells ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) such that:

• (i_1,j_1) = (1,1),(i_k,j_k) = (H,W);
• (i_{t+1},j_{t+1}) is an adjacent cell of (i_t,j_t) sharing a side, for all t\ (1 \leq t < k); and
• the letter written on (i_t,j_t) coincides with the (((t-1) \bmod 5) + 1)-th character of snuke, for all t\ (1 \leq t \leq k).

Constraints

• 2\leq H,W \leq 500
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.

Sample Input 1

2 3
sns
euk

Sample Output 1

Yes

The path (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) satisfies the conditions because they have s \rightarrow n \rightarrow u \rightarrow k written on them, in the order of visiting.

Sample Input 2

2 2
ab
cd

Sample Output 2

No

Sample Input 3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Sample Output 3

Yes

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\dots,A_N) consisting of 0, 1, and 2, and a length-N string S=S_1S_2\dots S_N consisting of M, E, and X.

Find the sum of \text{mex}(A_i,A_j,A_k) over all tuples of integers (i,j,k) such that 1 \leq i < j < k \leq N and S_iS_jS_k= MEX. Here, \text{mex}(A_i,A_j,A_k) denotes the minimum non-negative integer that equals neither A_i,A_j, nor A_k.

Constraints

• 3\leq N \leq 2\times 10^5
• N is an integer.
• A_i \in \lbrace 0,1,2\rbrace
• S is a string of length N consisting of M, E, and X.

Sample Input 1

4
1 1 0 2
MEEX

Sample Output 1

3

The tuples (i,j,k)\ (1 \leq i < j < k \leq N) such that S_iS_jS_k = MEX are the following two: (i,j,k)=(1,2,4),(1,3,4). Since \text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0 and \text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3, the answer is 0+3=3.

Sample Input 2

3
0 0 0
XXX

Sample Output 2

0

Sample Input 3

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

Sample Output 3

13

Problem Statement

You are in a store to buy N items. The regular price of the i-th item is P_i yen (the currency in Japan).

You have M coupons. You can use the i-th coupon to buy an item whose regular price is at least L_i yen at a D_i-yen discount.

Here, each coupon can be used only once. Besides, multiple coupons cannot be used for the same item.

If no coupon is used for an item, you will buy it for a regular price. Find the minimum possible total amount of money required to buy all the N items.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq P_i\leq 10^9
• 1\leq D_i \leq L_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
4 3 1
4 4 2
2 3 1

Sample Output 1

4

Consider using the 2-nd coupon for the 1-st item, and the 3-rd coupon for the 2-nd item.

Then, you buy the 1-st item for 4-3=1 yen, 2-nd item for 3-1=2 yen, and 3-rd item for 1 yen. Thus, you can buy all the items for 1+2+1=4 yen.

Sample Input 2

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

Sample Output 2

37

Problem Statement

There is a blackboard on which you can write integers. Initially, no integer is written on the blackboard. Given Q queries, process them in order.

The query is of one of the following three kinds:

• 1 x : write an x on the blackboard.

• 2 x : erase an x from the blackboard. At the point this query is given, it is guaranteed that at least one x is written on the blackboard.

• 3 : print the minimum possible bitwise XOR of two of the integers written on the blackboard. At the point this query is processed, it is guaranteed that at least two integers are written on the blackboard.

Constraints

• 1\leq Q \leq 3\times 10^5
• 0\leq x < 2 ^{30}
• When a query 2 is given, at least one x is written on the blackboard.
• When a query 3 is given, at least two integers are written on the blackboard.
• All input values are integers.

Sample Input 1

9
1 2
1 10
3
1 3
3
2 2
3
1 10
3

Sample Output 1

8
1
9
0

After processing the 1-st query, a 2 is written on the blackboard.

After processing the 2-nd query, a 2 and a 10 are written on the blackboard.

When processing the 3-rd query, the minimum possible bitwise XOR of two of the integers written on the backboard is 2\oplus 10=8.

After processing the 4-th query, a 2, a 3, and a 10 are written on the blackboard.

When processing the 5-th query, the minimum possible bitwise XOR of two of the integers written on the backboard is 2\oplus 3=1.

After processing the 6-th query, a 3 and a 10 are written on the blackboard.

When processing the 7-th query, the minimum possible bitwise XOR of two of the integers written on the backboard is 3\oplus 10=9.

After processing the 8-th query, a 3 and two 10s are written on the blackboard.

When processing the 9-th query, the minimum possible bitwise XOR of two of the integers written on the backboard is 10\oplus 10=0.

Problem Statement

There is a simple undirected graph with N vertices and M edges. The edges are initially painted white. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertex A_i and vertex B_i, and the cost required to paint it black is C_i.

"Making a Q" means painting four or more edges so that:

• all but one of the edges painted black form a simple cycle, and
• the edge painted black not forming the cycle connects a vertex on the cycle and another not on the cycle.

Determine if one can make a Q. If one can, find the minimum total cost required to make a Q.

Constraints

• 4\leq N \leq 300
• 4\leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• (A_i,B_i) \neq (A_j,B_j), if i \neq j.
• 1 \leq C_i \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

15

By painting edges 2,3,4,5, and 6,

• edges 2,4,5, and 6 forms a simple cycle, and
• edge 3 connects vertex 3 (on the cycle) and vertex 1 (not on the cycle),

so one can make a Q with a total cost of 4+5+3+2+1=15. Making a Q in another way costs 15 or greater, so the answer is 15.

Sample Input 2

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

Sample Output 2

-1

Sample Input 3

6 15
2 6 48772
2 4 36426
1 6 94325
3 6 3497
2 3 60522
4 5 63982
4 6 4784
1 2 14575
5 6 68417
1 5 7775
3 4 33447
3 5 90629
1 4 47202
1 3 90081
2 5 79445

Sample Output 3

78154