Problem Statement

You are given a string S consisting of lowercase English letters.

Here, we define the number of dots in a lowercase English letter as follows:

• If the lowercase English letter is i or j: 1 dot
• If the lowercase English letter is neither i nor j: 0 dots

Find the sum of the numbers of dots over all characters in S.

Constraints

• S is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

aiiaj

Sample Output 1

3

The numbers of dots in a, i, i, a, j are 0, 1, 1, 0, 1, respectively.

We have 0 + 1 + 1 + 0 + 1 = 3, so print 3.

Sample Input 2

abcedfgh

Sample Output 2

0

Sample Input 3

jjjjjj

Sample Output 3

6

Problem Statement

You are given a real number X.Y, where Y is a single digit.

Print the following: (quotes for clarity)

• X-, if 0 \leq Y \leq 2;
• X, if 3 \leq Y \leq 6;
• X+, if 7 \leq Y \leq 9.

Constraints

• 1 \leq X \leq 15
• 0 \leq Y \leq 9
• X and Y are integers.

Sample Input 1

15.8

Sample Output 1

15+

Here, printing 15 + will not be accepted: do not print a space between X and +, or between X and -.

Sample Input 2

1.0

Sample Output 2

1-

You will not get inputs such as 1.00 and 1.

Sample Input 3

12.5

Sample Output 3

12

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

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

• 2 \leq N \leq 100
• A_{i,j} \in \lbrace 0,1 \rbrace
• A_{i,i} = 0
• A_{i,j} = A_{j,i}
• All input values are integers.

Sample Input 1

4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

Sample Output 1

2 3
1 4
1
2

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

5
0 1 0 1 1
1 0 0 1 0
0 0 0 0 1
1 1 0 0 1
1 0 1 1 0

Sample Output 3

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

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\dots,N and the edges are numbered 1,2,\dots,M. Edge i connects vertices A_i and B_i.

Determine whether this graph is a cycle graph.

Constraints

• 3 \le N \le 2\times 10^5
• 0 \le M \le 2\times 10^5
• 1 \le A_i, B_i \le N
• The given graph is simple.
• All input values are integers.

Sample Input 1

4 4
2 4
3 1
4 1
2 3

Sample Output 1

Yes

The given graph is as follows, and this is a cycle graph.

Sample Input 2

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

Sample Output 2

No

The given graph is as follows, and this is not a cycle graph.

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

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

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

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

You are given an undirected graph with N vertices and zero edges.
The vertices are numbered 1,2,\dots,N, and initially all vertices are white.
Process a total of Q queries of the following three types:

• Type 1 : Add an undirected edge connecting vertices u and v.
• Type 2 : If vertex v is white, change it to black; if it is black, change it to white.
• Type 3 : Determine whether a black vertex can be reached from vertex v by traversing zero or more edges; report Yes if reachable, and No otherwise.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le Q \le 6 \times 10^5
• Type 1 queries satisfy the following constraints:
  • 1 \le u < v \le N
  • For each query, no edge connecting u and v has been added before that query.
• Type 2,3 queries satisfy the following constraints:
  • 1 \le v \le N

Sample Input 1

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

Sample Output 1

No
Yes
No
Yes
Yes
No

In this input, the graph initially has five vertices and zero edges.
This input contains 12 queries.

• The 1st query is 3 2.
  • At this point, no black vertex can be reached from vertex 2 by traversing zero or more edges, so report No.
• The 2nd query is 2 2.
  • Vertex 2 is white, so change it to black.
• The 3rd query is 3 2.
  • At this point, black vertex 2 can be reached from vertex 2 by traversing zero or more edges. Therefore, report Yes.
• The 4th query is 1 2 5.
  • Add an edge connecting vertices 2,5.
• The 5th query is 1 3 4.
  • Add an edge connecting vertices 3,4.
• The 6th query is 3 4.
  • At this point, no black vertex can be reached from vertex 4 by traversing zero or more edges, so report No.
• The 7th query is 3 5.
  • At this point, black vertex 2 can be reached from vertex 5 by traversing zero or more edges. Therefore, report Yes.
• The 8th query is 1 4 5.
  • Add an edge connecting vertices 4,5.
• The 9th query is 1 1 3.
  • Add an edge connecting vertices 1,3.
• The 10th query is 3 1.
  • At this point, black vertex 2 can be reached from vertex 1 by traversing zero or more edges. Therefore, report Yes.
• The 11th query is 2 2.
  • Vertex 2 is black, so change it to white.
• The 12th query is 3 1.
  • At this point, no black vertex can be reached from vertex 1 by traversing zero or more edges, so report No.

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.