Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

• remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 100
• 1 \leq A_i \leq 100
• All values in the input are integers.

Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.

Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0

Problem Statement

You are given a string S consisting of <, =, and >.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <, k =s, and one >, in this order, with a length of (k+2).

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of <, =, and >.

Sample Input 1

<====>

Sample Output 1

Yes

<====> is a concatenation of one <, four =s, and one >, in this order, so it is a bidirectional arrow string.
Hence, print Yes.

Sample Input 2

==>

Sample Output 2

No

==> does not meet the condition for a bidirectional arrow string.
Hence, print No.

Sample Input 3

<>>

Sample Output 3

No

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_{3N}) of length 3N where each of 1,2,\dots, and N occurs exactly three times.

For i=1,2,\dots,N, let f(i) be the index of the middle occurrence of i in A. Sort 1,2,\dots,N in ascending order of f(i).

Formally, f(i) is defined as follows.

• Suppose that those j such that A_j = i are j=\alpha,\beta,\gamma\ (\alpha < \beta < \gamma). Then, f(i) = \beta.

Constraints

• 1\leq N \leq 10^5
• 1 \leq A_j \leq N
• i occurs in A exactly three times, for each i=1,2,\dots,N.
• All input values are integers.

Sample Input 1

3
1 1 3 2 3 2 2 3 1

Sample Output 1

1 3 2

• 1 occurs in A at A_1,A_2,A_9, so f(1) = 2.
• 2 occurs in A at A_4,A_6,A_7, so f(2) = 6.
• 3 occurs in A at A_3,A_5,A_8, so f(3) = 5.

Thus, f(1) < f(3) < f(2), so 1,3, and 2 should be printed in this order.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3 4 1 2

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

• 2 \leq M \leq N \leq 10^5
• N and M are integers.
• S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• S_i \neq S_j \, (i \neq j)
• T_1 = S_1 and T_M = S_N.
• (T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

Problem Statement

There are N ants on a number line, labeled 1 to N. Ant i (1 \leq i \leq N) starts at coordinate X_i and faces either a positive or negative direction. Initially, all ants are at distinct coordinates. The direction each ant is facing is represented by a binary string S of length N, where ant i is facing the negative direction if S_i is 0 and the positive direction if S_i is 1.

Let the current time be 0, and the ants move in their respective directions at a speed of 1 unit per unit time for (T+0.1) units of time until time (T+0.1). If multiple ants reach the same coordinate, they pass through each other without changing direction or speed. After (T+0.1) units of time, all ants stop.

Find the number of pairs (i, j) such that 1 \leq i < j \leq N and ants i and j pass each other from now before time (T+0.1).

Constraints

• 2 \leq N \leq 2 \times 10^{5}
• 1 \leq T \leq 10^{9}
• S is a string of length N consisting of 0 and 1.
• -10^{9} \leq X_i \leq 10^{9} (1 \leq i \leq N)
• X_i \neq X_j (1 \leq i < j \leq N)
• N, T, and X_i (1 \leq i \leq N) are integers.

Sample Input 1

6 3
101010
-5 -1 0 1 2 4

Sample Output 1

5

The following five pairs of ants pass each other:

• Ant 3 and ant 4 pass each other at time 0.5.
• Ant 5 and ant 6 pass each other at time 1.
• Ant 1 and ant 2 pass each other at time 2.
• Ant 3 and ant 6 pass each other at time 2.
• Ant 1 and ant 4 pass each other at time 3.

No other pairs of ants pass each other, so print 5.

Sample Input 2

13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

Sample Output 2

14

Problem Statement

You are given an undirected graph consisting of N vertices and M edges.
For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertex u_i and v_i that is initially passable if a_i = 1 and initially impassable if a_i = 0. Additionally, there are switches on K of the vertices: vertex s_1, vertex s_2, \ldots, vertex s_K.

Takahashi is initially on vertex 1, and will repeat performing one of the two actions below, Move or Hit Switch, which he may choose each time, as many times as he wants.

• Move: Choose a vertex adjacent to the vertex he is currently on via an edge, and move to that vertex.
• Hit Switch: If there is a switch on the vertex he is currently on, hit it. This will invert the passability of every edge in the graph. That is, a passable edge will become impassable, and vice versa.

Determine whether Takahashi can reach vertex N, and if he can, print the minimum possible number of times he performs Move before reaching vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• a_i \in \lbrace 0, 1\rbrace
• 1 \leq s_1 \lt s_2 \lt \cdots \lt s_K \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5

Takahashi can reach vertex N as follows.

• Move from vertex 1 to vertex 2.
• Move from vertex 2 to vertex 3.
• Hit the switch on vertex 3. This inverts the passability of every edge in the graph.
• Move from vertex 3 to vertex 1.
• Move from vertex 1 to vertex 4.
• Hit the switch on vertex 4. This again inverts the passability of every edge in the graph.
• Move from vertex 4 to vertex 5.

Here, Move is performed five times, which is the minimum possible number.

Sample Input 2

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

Sample Output 2

-1

The given graph may be disconnected or contain multi-edges. In this sample input, there is no way for Takahashi to reach vertex N, so you should print -1.

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507