Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

• S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

Problem Statement

You are given N integers A_1, A_2, \ldots, A_N. Find the largest among those integers that are not the largest.

The constraints of this problem guarantee that the answer exists.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• It is not the case that all A_1, A_2, \ldots, A_N are equal.
• All input values are integers.

Sample Input 1

5
2 1 3 3 2

Sample Output 1

2

The largest integer among 2,1,3,3,2 is 3.

The integers that are not 3 among 2,1,3,3,2 are 2,1,2, among which the largest is 2.

Sample Input 2

4
4 3 2 1

Sample Output 2

3

Sample Input 3

8
22 22 18 16 22 18 18 22

Sample Output 3

18

Problem Statement

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

Find the number of non-empty substrings of S that are repetitions of one character. Here, two substrings that are equal as strings are not distinguished even if they are obtained differently.

A non-empty substring of S is a string of length at least one obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, ab and abc are non-empty substrings of abc, while ac and the empty string are not.

Constraints

• 1 \leq N \leq 2\times 10^5
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

6
aaabaa

Sample Output 1

4

The non-empty substrings of S that are repetitions of one character are a, aa, aaa, and b; there are four of them. Note that there are multiple ways to obtain a or aa from S, but each should only be counted once.

Sample Input 2

1
x

Sample Output 2

1

Sample Input 3

12
ssskkyskkkky

Sample Output 3

8

Problem Statement

There is an election to choose one winner from N candidates with candidate numbers 1, 2, \ldots, N, and there have been M votes cast.

Each vote is for exactly one candidate, with the i-th vote being for candidate A_i.

The votes will be counted in order from first to last, and after each vote is counted, the current winner will be updated and displayed.

The candidate with the most votes among those counted is the winner. If there are multiple candidates with the most votes, the one with the smallest candidate number is the winner.

For each i = 1, 2, \ldots, M, determine the winner when counting only the first i votes.

Constraints

• 1 \leq N, M \leq 200000
• 1 \leq A_i \leq N
• All input values are integers.

Sample Input 1

3 7
1 2 2 3 1 3 3

Sample Output 1

1
1
2
2
1
1
3

Let C_i denote the number of votes for candidate i.

• After the first vote is counted, (C_1, C_2, C_3) = (1, 0, 0), so the winner is 1.
• After the second vote is counted, (C_1, C_2, C_3) = (1, 1, 0), so the winner is 1.
• After the third vote is counted, (C_1, C_2, C_3) = (1, 2, 0), so the winner is 2.
• After the fourth vote is counted, (C_1, C_2, C_3) = (1, 2, 1), so the winner is 2.
• After the fifth vote is counted, (C_1, C_2, C_3) = (2, 2, 1), so the winner is 1.
• After the sixth vote is counted, (C_1, C_2, C_3) = (2, 2, 2), so the winner is 1.
• After the seventh vote is counted, (C_1, C_2, C_3) = (2, 2, 3), so the winner is 3.

Sample Input 2

100 5
100 90 80 70 60

Sample Output 2

100
90
80
70
60

Sample Input 3

9 8
8 8 2 2 8 8 2 2

Sample Output 3

8
8
8
2
8
8
8
2

Problem Statement

You are given two strings: S, which consists of uppercase English letters and has length N, and T, which also consists of uppercase English letters and has length M\ (\leq N).

There is a string X of length N consisting only of the character #. Determine whether it is possible to make X match S by performing the following operation any number of times:

• Choose M consecutive characters in X and replace them with T.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq \min(N, 5)
• S is a string consisting of uppercase English letters with length N.
• T is a string consisting of uppercase English letters with length M.

Sample Input 1

7 3
ABCBABC
ABC

Sample Output 1

Yes

Below, let X[l:r] denote the part from the l-th through the r-th character of X.

You can make X match S by operating as follows.

1. Replace X[3:5] with T. X becomes ##ABC##.
2. Replace X[1:3] with T. X becomes ABCBC##.
3. Replace X[5:7] with T. X becomes ABCBABC.

Sample Input 2

7 3
ABBCABC
ABC

Sample Output 2

No

No matter how you operate, it is impossible to make X match S.

Sample Input 3

12 2
XYXXYXXYYYXY
XY

Sample Output 3

Yes

Problem Statement

There are N boxes numbered 1, 2, \ldots, N. Initially, box i contains one ball of color C_i.

You are given Q queries, which you should process in order.

Each query is given by a pair of integers (a,b) and asks you to do the following:

• Move all the balls from box a to box b, and then print the number of different colors of balls in box b.

Here, the boxes a and b may be empty.

Constraints

• 1 \leq N, Q \leq 200000
• 1 \leq C_i \leq N
• 1 \leq a, b \leq N
• a \neq b
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
2
1
1
3

• For the first query, move all the balls from box 1 to box 2. Box 2 now contains two balls of color 1, so print 1.

• For the second query, move all the balls from box 6 to box 4. Box 4 now contains one ball of color 2 and one ball of color 3, so print 2.

• For the third query, move all the balls from box 5 to box 1. Box 1 now contains one ball of color 2, so print 1.

• For the fourth query, move all the balls from box 3 to box 6. Box 6 now contains one ball of color 1, so print 1.

• For the fifth query, move all the balls from box 4 to box 6. Box 6 now contains one ball of color 1, one ball of color 2, and one ball of color 3, so print 3.

Sample Input 2

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

Sample Output 2

1
2
0

Problem Statement

You are given a binary tree with N vertices. The vertices are numbered 1 to N, with vertex 1 being the root. The i-th edge (1\leq i \leq N-1) connects vertex i+1 and vertex P_i\ (\leq i) bidirectionally.

There are one basket and M balls on this tree. The balls are numbered 1 to M, and each ball j has a designated start vertex S_j and goal vertex T_j. Initially, the basket is empty and placed at vertex 1, and the balls are placed at their respective start vertices.

You can perform the following operation any number of times in any order.

• Let v be the current vertex where the basket is placed. Do one of the following:
  • Choose one edge connected to vertex v, and move the basket along that edge to the adjacent vertex. The balls inside the basket move together with it.
  • Choose a ball with the start vertex v that is still placed at v, and put it into the basket. This operation can only be performed if the basket contains fewer than K balls (that is, the basket cannot contain K+1 or more balls).
  • Choose a ball with the goal vertex v from the basket and take it out, placing it at vertex v.

A sequence of operations is called a good operation sequence if and only if the basket is eventually empty and placed at vertex 1, and the balls are eventually placed at their respective goal vertices.

Since it is tiring to move the basket many times, the basket's movement path should traverse each edge exactly twice before returning to vertex 1. Find the number, modulo 998244353, of those paths such that a good operation sequence exists following that path.

Constraints

• 2\leq N \leq 10^4
• 1\leq M \leq 2\times 10^5
• 1\leq K \leq 10^3
• 1\leq P_i \leq i
• For every v\ (1\leq v \leq N), there are at most two i's such that P_i=v.
• 1\leq S_j, T_j \leq N
• S_j \neq T_j
• All input values are integers.

Sample Input 1

5 2 1
1 1 3 3
2 4
5 3

Sample Output 1

1

The given graph is shown in the figure below. The circles and squares written next to the vertices represent the start and goal vertices of the balls, respectively.

Among the paths where every edge is traversed exactly twice before returning to vertex 1, there is only one path such that a good operation sequence exists following that path, which is shown below:

Here, you can construct the following good operation sequence:

1. Move the basket to vertex 2.
2. Put ball 1 into the basket.
3. Move the basket to vertex 1.
4. Move the basket to vertex 3.
5. Move the basket to vertex 4.
6. Take ball 1 out of the basket and place it at vertex 4.
7. Move the basket to vertex 3.
8. Move the basket to vertex 5.
9. Put ball 2 into the basket.
10. Move the basket to vertex 3.
11. Take ball 2 out of the basket and place it at vertex 3.
12. Move the basket to vertex 1.

Sample Input 2

5 2 2
1 1 3 3
2 4
5 3

Sample Output 2

2

The value of K has increased by 1 from Sample Input 1. This allows you to construct a good operation sequence for the following path, in addition to the one illustrated above.

Sample Input 3

15 4 2
1 2 1 4 2 3 4 7 3 7 5 9 11 8
14 12
5 4
13 15
5 12

Sample Output 3

8