Problem Statement

You are given an integer sequence of length N: A = (A_1,A_2,\ldots,A_N).

Determine whether there is a place in A where the same element appears three or more times in a row.

More formally, determine whether there exists an integer i with 1 \le i \le N-2 such that A_i = A_{i+1} = A_{i+2}.

Constraints

• 3 \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

5
1 4 4 4 2

Sample Output 1

Yes

We have A=(1,4,4,4,2). There is a place where 4 appears three times in a row, so print Yes.

Sample Input 2

6
2 4 4 2 2 4

Sample Output 2

No

We have A=(2,4,4,2,2,4). There is no place where the same element appears three or more times in a row, so print No.

Sample Input 3

8
1 4 2 5 7 7 7 2

Sample Output 3

Yes

Sample Input 4

10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

No

Sample Input 5

13
1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

Yes

Problem Statement

You are given a sequence A = (A_1, A_2, \cdots , A_N) of length N.

After that, an integer X between 1 and N, inclusive, is given.

Output the value of A_X.

Constraints

• 1 \le X \le N \le 100
• 1 \le A_i \le 100
• All input values are integers.

Sample Input 1

5
1 2 3 4 5
3

Sample Output 1

3

We have (A_1, A_2, A_3, A_4 , A_5) = (1, 2, 3, 4, 5). Since A_3 = 3, output 3.

Sample Input 2

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

Sample Output 2

6

Sample Input 3

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

Sample Output 3

1

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq 100
• 1 \leq T \leq 100
• 1 \leq P \leq N
• All input values are integers.

Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.

Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.

Sample Input 3

3 10 1
1 2 3

Sample Output 3

7

Problem Statement

You are given an integer N.

Print all triples of non-negative integers (x,y,z) such that x+y+z\leq N in ascending lexicographical order.

Constraints

• 0 \leq N \leq 21
• N is an integer.

Sample Input 1

3

Sample Output 1

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

Sample Input 2

4

Sample Output 2

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

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

Takahashi is initially in room R, and can move between rooms i - 1 and i only when door i is unlocked. Also, he can perform a switching operation on door i only when he is in room i - 1 or room i. When a switching operation is performed on door i, if the door is unlocked, it becomes locked, and if it is locked, it becomes unlocked.

Find the minimum number of switching operations needed to make all doors locked.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq R \leq N
• L_i \in \lbrace 0, 1 \rbrace
• All input values are integers.

Sample Input 1

6 3
1 0 0 1 0 0

Sample Output 1

6

Takahashi can make all doors locked with six switching operations by acting as follows:

• Move to room 2.
• Perform a switching operation on door 2 to lock door 2.
• Move to room 3.
• Perform a switching operation on door 4 to unlock door 4.
• Perform a switching operation on door 3 to lock door 3.
• Move to room 4.
• Perform a switching operation on door 4 to lock door 4.
• Move to room 5.
• Perform a switching operation on door 5 to lock door 5.
• Perform a switching operation on door 6 to lock door 6.

Sample Input 2

2 1
0 0

Sample Output 2

2

Sample Input 3

8 2
0 1 0 0 1 0 1 1

Sample Output 3

8

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.

A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.

Constraints

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

Sample Input 1

4
3 6 9 3

Sample Output 1

8

There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).

Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

15

All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.

Sample Input 3

8
87 42 64 86 72 58 44 30

Sample Output 3

22

Problem Statement

There is a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
N squares, (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N), have walls.

Takahashi is initially at square (r_\mathrm{s}, c_\mathrm{s}).

Q instructions are given to Takahashi. For i = 1, 2, \ldots, Q, the i-th instruction is represented by a pair of a character d_i and a positive integer l_i. d_i is one of L, R, U, and D, representing the directions of left, right, up, and down, respectively.

Given the i-th direction, Takahashi repeats the following action l_i times:

If a square without a wall is adjacent to the current square in the direction represented by d_i, move to that square; otherwise, do nothing.

For i = 1, 2, \ldots, Q, print the square where Takahashi will be after he follows the first i instructions.

Constraints

• 2 \leq H, W \leq 10^9
• 1 \leq r_\mathrm{s} \leq H
• 1 \leq c_\mathrm{s} \leq W
• 0 \leq N \leq 2 \times 10^5
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• (r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i) for all i = 1, 2, \ldots, N.
• 1 \leq Q \leq 2 \times 10^5
• d_i is one of the characters L, R, U, and D.
• 1 \leq l_i \leq 10^9
• All values in the input other than d_i are integers.

Sample Input 1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

Sample Output 1

4 2
3 2
3 1
3 5

The given grid and the initial position of Takahashi are as follows, where # denotes a square with a wall, T a square where Takahashi is, and . the other squares:

...#.
.#...
.....
...T.
..#..

Given the 1-st instruction, Takahashi moves 2 squares to the left, ending up in square (4, 2) as follows:

...#.
.#...
.....
.T...
..#..

Given the 2-nd instruction, Takahashi first moves 1 square upward, then he "does nothing" twice because the adjacent square in his direction has a wall. As a result, he ends up in square (3, 2) as follows:

...#.
.#...
.T...
.....
..#..

Given the 3-rd instruction, Takahashi first moves 1 square to the left, then he "does nothing" once because there is no square in his direction. As a result, he ends up in square (3, 1) as follows:

...#.
.#...
T....
.....
..#..

Given the 4-th instruction, Takahashi moves 4 squares to the right, ending up in square (3, 5) as follows:

...#.
.#...
....T
.....
..#..

Sample Input 2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

Sample Output 2

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

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 is a graph G with N vertices and 0 edges on a 2-dimensional plane. The vertices are numbered from 1 to N, and vertex i is located at coordinates (x_i,y_i).

For vertices u and v of G, the distance d(u,v) between u and v is defined as the Manhattan distance d(u,v)=|x_u-x_v|+|y_u-y_v|.

Also, for two connected components A and B of G, let V(A) and V(B) be the vertex sets of A and B, respectively. The distance d(A,B) between A and B is defined as d(A,B)=\min\lbrace d(u,v)\mid u \in V(A), v\in V(B)\rbrace.

Process Q queries as described below. Each query is one of the following three types:

• 1 a b : Let n be the number of vertices in G. Add vertex n+1 to G with coordinates (x_{n+1},y_{n+1})=(a,b).
• 2 : Let n be the number of vertices in G and m be the number of connected components.
  • If m=1, output -1.
  • If m\geq 2, merge all connected components with the minimum distance and output the value of that minimum distance. Formally, let the connected components of G be A_1,A_2,\ldots,A_m and let \displaystyle k=\min_{1\leq i\lt j\leq m} d(A_i,A_j). For all pairs of vertices (u,v)\ (1\leq u\lt v\leq n) that are not in the same connected component and satisfy d(u,v)=k, add an edge between vertices u and v. Then, output k.
• 3 u v : If vertices u and v are in the same connected component, output Yes; otherwise, output No.

Constraints

• 2\leq N\leq 1500
• 1\leq Q\leq 1500
• 0\leq x_i,y_i\leq 10^9
• For queries of type 1, 0\leq a,b\leq 10^9.
• For queries of type 3, let n be the number of vertices in G just before processing that query, then 1\leq u\lt v\leq n.
• All input values are integers.

Sample Input 1

4 11
3 4
3 3
7 3
2 2
3 1 2
2
3 1 2
1 6 4
2
3 2 5
2
3 2 5
2
1 2 2
2

Sample Output 1

No
1
Yes
2
No
3
Yes
-1
0

Initially, vertices 1,2,3,4 are located at coordinates (3,4),(3,3),(7,3),(2,2), respectively.

• For the 1st query, vertices 1 and 2 are not connected, so output No.
• For the 2nd query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 3\rbrace, \lbrace 4\rbrace. The minimum distance between different connected components is 1, and an edge is added between vertices 1 and 2. Output 1.
• For the 3rd query, vertices 1 and 2 are connected, so output Yes.
• For the 4th query, add vertex 5 at coordinates (6,4).
• For the 5th query, there are 4 connected components, and the vertex set of each connected component is \lbrace 1,2\rbrace,\lbrace 3\rbrace,\lbrace 4\rbrace,\lbrace 5\rbrace. The minimum distance between different connected components is 2, and edges are added between vertices 2 and 4 and between vertices 3 and 5. Output 2.
• For the 6th query, vertices 2 and 5 are not connected, so output No.
• For the 7th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,4\rbrace,\lbrace 3,5\rbrace. The minimum distance between different connected components is 3, and an edge is added between vertices 1 and 5. Output 3.
• For the 8th query, vertices 2 and 5 are connected, so output Yes.
• For the 9th query, there is 1 connected component, so output -1.
• For the 10th query, add vertex 6 at coordinates (2,2).
• For the 11th query, there are 2 connected components, and the vertex set of each connected component is \lbrace 1,2,3,4,5\rbrace,\lbrace 6\rbrace. The minimum distance between different connected components is 0, and an edge is added between vertices 4 and 6. Output 0.