Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

• First, he painted the part from X=L_1 to X=R_1 red.
• Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

• 0\leq L_1<R_1\leq 100
• 0\leq L_2<R_2\leq 100
• All values in input are integers.

Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

Problem Statement

N players played a round-robin tournament.

You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.

Determine whether the given table is contradictory.

The table is said to be contradictory when some of the following holds:

• There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
• There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
• There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.

Constraints

• 2 \leq N \leq 1000
• A_{i,i} is -.
• A_{i,j} is W, L, or D, for i\neq j.

Sample Input 1

4
-WWW
L-DD
LD-W
LDW-

Sample Output 1

incorrect

Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.

Sample Input 2

2
-D
D-

Sample Output 2

correct

There is no contradiction.

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

Takahashi will toss a coin N times. He also has a counter, which initially shows 0.

Depending on the result of the i-th coin toss, the following happens:

• If it heads: Takahashi increases the counter's value by 1 and receives X_i yen (Japanese currency).
• If it tails: he resets the counter's value to 0, without receiving money.

Additionally, there are M kinds of streak bonuses. The i-th kind of streak bonus awards Y_i yen each time the counter shows C_i.

Find the maximum amount of money that Takahashi can receive.

Constraints

• 1\leq M\leq N\leq 5000
• 1\leq X_i\leq 10^9
• 1\leq C_i\leq N
• 1\leq Y_i\leq 10^9
• C_1,C_2,\ldots,C_M are all different.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

48

If he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.

• In the 1-st coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 2 yen.
• In the 2-nd coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 7 yen. Additionally, get 10 yen as a streak bonus.
• In the 3-rd coin toss, the coin tails. Change the counter's value from 2 to 0.
• In the 4-th coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 8 yen.
• In the 5-th coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 2 yen. Additionally, get 10 yen as a streak bonus.
• In the 6-th coin toss, the coin heads. Change the counter's value from 2 to 3 and receive 8 yen. Additionally, get 1 yen as a streak bonus.

In this case, Takahashi receives 2+(7+10)+0+8+(2+10)+(8+1)=48 yen in total, which is the maximum possible.
Note that streak bonuses are awarded any number of times each time the counter shows C_i.
As a side note, if he gets head in all 6 coin tosses, he only receives 2+(7+10)+(1+1)+8+(2+5)+8=44 yen, which is not the maximum.

Sample Input 2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (T_i,A_i), and is the following operation:

• if T_i=1, it replaces the value of X with X\ {\rm and}\ A_i;
• if T_i=2, it replaces the value of X with X\ {\rm or}\ A_i;
• if T_i=3, it replaces the value of X with X\ {\rm xor}\ A_i.

Initialize X with the value of C and execute the following procedures in order:

• Perform Operation 1, and then print the resulting value of X.
• Next, perform Operation 1, 2 in this order, and then print the value of X.
• Next, perform Operation 1, 2, 3 in this order, and then print the value of X.
• \vdots
• Next, perform Operation 1, 2, \ldots, N in this order, and then print the value of X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1\leq T_i \leq 3
• 0\leq A_i \lt 2^{30}
• 0\leq C \lt 2^{30}
• All values in input are integers.

Sample Input 1

3 10
3 3
2 5
1 12

Sample Output 1

9
15
12

The initial value of X is 10.

• Operation 1 changes X to 9.
• Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
• Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.

Sample Input 2

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

Sample Output 2

0
2
1
0
5
3
3
11
2

Problem Statement

There are N balls arranged from left to right. The color of the i-th ball from the left is Color C_i, and an integer X_i is written on it.

Takahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every 1\leq i\leq N-1, the number written on the (i+1)-th ball from the left is greater than or equal to the number written on the i-th ball from the left.

For this, Takahashi can repeat the following operation any number of times (possibly zero):

Choose an integer i such that 1\leq i\leq N-1.
If the colors of the i-th and (i+1)-th balls from the left are different, pay a cost of 1. (No cost is incurred if the colors are the same).
Swap the i-th and (i+1)-th balls from the left.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1\leq C_i\leq N
• 1\leq X_i\leq N
• All values in input are integers.

Sample Input 1

5
1 5 2 2 1
3 2 1 2 1

Sample Output 1

6

Let us represent a ball as (Color, Integer). The initial situation is (1,3), (5,2), (2,1), (2,2), (1,1). Here is a possible sequence of operations for Takahashi:

• Swap the 1-st ball (Color 1) and 2-nd ball (Color 5). Now the balls are arranged in the order (5,2), (1,3), (2,1), (2,2), (1,1).
• Swap the 2-nd ball (Color 1) and 3-rd ball (Color 2). Now the balls are arranged in the order (5,2), (2,1), (1,3), (2,2), (1,1).
• Swap the 3-rd ball (Color 1) and 4-th ball (Color 2). Now the balls are in the order (5,2), (2,1), (2,2), (1,3), (1,1).
• Swap the 4-th ball (Color 1) and 5-th ball (Color 1). Now the balls are in the order (5,2), (2,1), (2,2), (1,1), (1,3).
• Swap the 3-rd ball (Color 2) and 4-th ball (Color 1). Now the balls are in the order(5,2), (2,1), (1,1), (2,2), (1,3).
• Swap the 1-st ball (Color 5) and 2-nd ball (Color 2). Now the balls are in the order (2,1), (5,2), (1,1), (2,2), (1,3).
• Swap the 2-nd ball (Color 5) and 3-rd ball (Color 1). Now the balls are in the order (2,1), (1,1), (5,2), (2,2), (1,3).

After the last operation, the numbers written on the balls are 1,1,2,2,3 from left to right, which achieves Takahashi's objective.

The 1-st, 2-nd, 3-rd, 5-th, 6-th, and 7-th operations incur a cost of 1 each, for a total of 6, which is the minimum. Note that the 4-th operation does not incur a cost since the balls are both in Color 1.

Sample Input 2

3
1 1 1
3 2 1

Sample Output 2

0

All balls are in the same color, so no cost is incurred in swapping balls.

Sample Input 3

3
3 1 2
1 1 2

Sample Output 3

0

Takahashi's objective is already achieved without any operation.

Problem Statement

You are given two strings S and T consisting of lowercase English letters.

Takahashi starts with the string S. He can perform K kinds of operations any number of times in any order.
The i-th operation is the following:

Pay a cost of 1. Then, if the current string contains the character C_i, choose one of its occurrences and replace it with the string A_i. Otherwise, do nothing.

Find the minimum total cost needed to make the string equal T. If it is impossible to do so, print -1.

Constraints

• 1\leq |S|\leq |T|\leq 50
• 1\leq K\leq 50
• C_i is a, b,\ldots, or z.
• 1\leq |A_i|\leq 50
• S, T, and A_i are strings consisting of lowercase English letters.
• C_i\neq A_i, regarding C_i as a string of length 1.
• All pairs (C_i,A_i) are distinct.

Sample Input 1

ab
cbca
3
a b
b ca
a efg

Sample Output 1

4

Starting with S=ab, Takahashi can make T=cbca in four operations as follows:

• Replace the 1-st character a in ab with b (Operation of the 1-st kind). The string is now bb.
• Replace the 2-nd character b in bb with ca (Operation of the 2-nd kind). The string is now bca.
• Replace the 1-st character b in bca with ca (Operation of the 2-nd kind). The string is now caca.
• Replace the 2-nd character a in caca with b (Operation of the 1-st kind). The string is now cbca.

Each operation incurs a cost of 1, for a total of 4, which is the minimum possible.

Sample Input 2

a
aaaaa
2
a aa
a aaa

Sample Output 2

2

Two operations a \to aaa \to aaaaa incur a cost of 2, which is the minimum possible.

Sample Input 3

a
z
1
a abc

Sample Output 3

-1

No sequence of operations makes T=z from S=a.

Problem Statement

We have a directed graph with N vertices and M edges. Edge i is directed from Vertex A_i to B_i and has a weight of C_i.

Initially, there is a piece on Vertex v. Takahashi and Aoki will play a game where they alternate turns moving the piece as follows:

• If there is no edge that goes from the vertex on which the piece is placed, end the game.
• If there are edges that go from the vertex on which the piece is placed, choose one of those edges and move the piece along that edge.

Takahashi goes first. Takahashi tries to minimize the total weight of the edges traversed by the piece, and Aoki tries to maximize it.
More formally, their objectives are as follows.
Takahashi gives the first priority to ending the game in a finite number of moves. If this is possible, he tries to minimize the total weight of the edges traversed by the piece.
Aoki gives the first priority to preventing the game from ending in a finite number of moves. If this is impossible, he tries to maximize the total weight of the edges traversed by the piece.
(If the piece traverses the same edge multiple times, the weight is added that number of times.)

Determine whether the game ends in a finite number of moves when both players play optimally. If it ends, find the total weight of the edges traversed by the piece.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1 \leq v \leq N
• 1 \leq A_i,B_i \leq N
• There is no multi-edges. That is, (A_i,B_i)\neq(A_j,B_j) for i\neq j.
• There is no self-loops. That is, A_i\neq B_i.
• 0 \leq C_i \leq 10^9
• All values in input are integers.

Sample Input 1

7 6 1
1 2 1
1 3 10
2 4 100
2 5 102
3 6 20
3 7 30

Sample Output 1

40

First, Takahashi will move the piece to Vertex 3. Next, Aoki will move the piece to Vertex 7, and the game will end.
The total weight of the edges traversed by the piece will be 10+30=40.

Sample Input 2

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

Sample Output 2

INFINITY

The game will not end in a finite number of moves.

Sample Input 3

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

Sample Output 3

5

The piece will go 1\to 2 \to 3 \to 1 \to 2\to 4.