Problem Statement

There are three brothers named A, B, and C. The age relationships among them are given by three characters S_{\mathrm{AB}}, S_{\mathrm{AC}}, S_{\mathrm{BC}}, which mean the following:

• If S_{\mathrm{AB}} is <, then A is younger than B; if it is >, then A is older than B.
• If S_{\mathrm{AC}} is <, then A is younger than C; if it is >, then A is older than C.
• If S_{\mathrm{BC}} is <, then B is younger than C; if it is >, then B is older than C.

Who is the middle brother, that is, the second oldest among the three?

Constraints

• Each of S_{\mathrm{AB}}, S_{\mathrm{AC}}, S_{\mathrm{BC}} is < or >.
• The input contains no contradictions; that is, there always exists an age relationship that satisfies all given inequalities.

Sample Input 1

< < <

Sample Output 1

B

Since A is younger than B, and B is younger than C, we can determine that C is the oldest, B is the middle, and A is the youngest. Hence, the answer is B.

Sample Input 2

< < >

Sample Output 2

C

Problem Statement

In the Kingdom of AtCoder, the eldest son is always given the name Taro. No one else is given the name Taro. The eldest son is the earliest born male child in each family.

There are N families in the Kingdom, and M babies were born. Before the M babies were born, none of the N families had had any babies.

Information about the babies is given in chronological order of their birth.

The i-th baby born was born in family A_i, and the baby is male if B_i is M, and female if it is F.

Determine for each of the M babies whether the name given is Taro.

Constraints

• 1\leq N,M\leq 100
• 1\leq A_i\leq N
• B_i is M or F.
• All numbers in the input are integers.

Sample Input 1

2 4
1 M
1 M
2 F
2 M

Sample Output 1

Yes
No
No
Yes

The first baby is the earliest born boy in family 1, so he is named Taro.

The second baby is not the earliest born boy in family 1, so he is not named Taro.

The third baby is a girl, so she is not named Taro.

The fourth baby is the earliest born boy in family 2, so he is named Taro. Note that the third baby is also born in family 2, but it is the earliest born boy who is named Taro.

Sample Input 2

4 7
2 M
3 M
1 F
4 F
4 F
1 F
2 M

Sample Output 2

Yes
Yes
No
No
No
No
No

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

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

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

There are N villages on a number line. The i-th village is located at coordinate X_i, and has P_i villagers.

Answer Q queries. The i-th query is in the following format:

• Given integers L_i and R_i, find the total number of villagers living in villages located between coordinates L_i and R_i, inclusive.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• -10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
• 1\leq P_i\leq 10^9
• -10^9\leq L_i \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

4
1 3 5 7
1 2 3 4
4
1 1
2 6
0 10
2 2

Sample Output 1

1
5
10
0

Consider the first query. The villages between coordinates 1 and 1 are the village at coordinate 1, with 1 villager. Hence, the answer is 1.

Consider the second query. The villages between coordinates 2 and 6 are the villages at coordinates 3 and 5, with 2 and 3 villagers, respectively. Hence, the answer is 2+3=5.

Sample Input 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

Sample Output 2

26
15
7
26
18
28
26
11

Problem Statement

You are given a sequence of integers A = (A_1, A_2, \ldots, A_N) of length N. Define f(l, r) as:

• the number of distinct values in the subsequence (A_l, A_{l+1}, \ldots, A_r).

Evaluate the following expression:

Constraints

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

Sample Input 1

3
1 2 2

Sample Output 1

8

Consider f(1,2). The subsequence (A_1, A_2) = (1,2) contains 2 distinct values, so f(1,2)=2.

Consider f(2,3). The subsequence (A_2, A_3) = (2,2) contains 1 distinct value, so f(2,3)=1.

The sum of f is 8.

Sample Input 2

9
5 4 2 2 3 2 4 4 1

Sample Output 2

111

Problem Statement

There is a road extending east and west, and N persons are on the road. The road extends infinitely long to the east and west from a point called the origin.

The i-th person (1\leq i\leq N) is initially at a position X_i meters east from the origin.

The persons can move along the road to the east or west. Specifically, they can perform the following movement any number of times.

• Choose one person. If there is no other person at the destination, move the chosen person 1 meter east or west.

They have Q tasks in total, and the i-th task (1\leq i\leq Q) is as follows.

• The T_i-th person arrives at coordinate G_i.

Find the minimum total number of movements required to complete all Q tasks in order.

Constraints

• 1\leq N\leq2\times10^5
• 0\leq X_1 < X_2 < \dotsb < X_N \leq10^8
• 1\leq Q\leq2\times10^5
• 1\leq T_i\leq N\ (1\leq i\leq Q)
• 0\leq G_i\leq10^8\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

5
10 20 30 40 50
4
3 45
4 20
1 35
2 60

Sample Output 1

239

An optimal sequence of movements for the persons is as follows (the positions of the persons are not necessarily drawn to scale):

For each task, the persons move as follows.

• The 4th person moves 6 steps east, and the 3rd person moves 15 steps east.
• The 2nd person moves 2 steps west, the 3rd person moves 26 steps west, and the 4th person moves 26 steps west.
• The 4th person moves 18 steps east, the 3rd person moves 18 steps east, the 2nd person moves 18 steps east, and the 1st person moves 25 steps east.
• The 5th person moves 13 steps east, the 4th person moves 24 steps east, the 3rd person moves 24 steps east, and the 2nd person moves 24 steps east.

The total number of movements is 21+54+79+85=239.

You cannot complete all tasks with a total movement count of 238 or less, so print 239.

Sample Input 2

8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578

Sample Output 2

4294967297

Note that some persons may need to move to the west of the origin or more than 10^8 meters to the east of it.

Also, note that the answer may exceed 2^{32}.

Sample Input 3

12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996

Sample Output 3

89644

Problem Statement

You are given permutations P = (P_1, P_2, \ldots, P_N) and A = (A_1, A_2, \ldots, A_N) of (1,2,\ldots,N).

You can perform the following operation any number of times, possibly zero:

• replace A_i with A_{P_i} simultaneously for all i=1,2,\ldots,N.

Print the lexicographically smallest A that can be obtained.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq P_i\leq N\ (1\leq i\leq N)
• P_i\neq P_j\ (1\leq i<j\leq N)
• 1\leq A_i\leq N\ (1\leq i\leq N)
• A_i\neq A_j\ (1\leq i<j\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

1 4 2 5 3 6

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

Repeating the operation yields the following.

• A = (1, 4, 2, 5, 3, 6)
• A = (2, 1, 3, 6, 4, 5)
• A = (3, 2, 4, 5, 1, 6)
• A = (4, 3, 1, 6, 2, 5)

After this, A will revert to the original state every four operations.

Therefore, print the lexicographically smallest among these, which is 1 4 2 5 3 6.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8

You may choose to perform no operations.

Sample Input 3

26
24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10
15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17

Sample Output 3

4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8