Problem Statement

Takahashi is enjoying a game at school. The game starts at the moment the bell rings.

Immediately after the bell rings, he repeats the following actions:

• Run at a speed of S meters per second for A seconds. Then, remain stationary for B seconds.

How many meters in total does he run by the time X seconds have elapsed since the bell rang?

Constraints

• 1 \leq S \leq 15
• 1 \leq A \leq 1000
• 1 \leq B \leq 1000
• 1 \leq X \leq 1000
• All input values are integers.

Sample Input 1

7 3 2 11

Sample Output 1

49

During the 11 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 3 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
• From 3 seconds to 5 seconds, he remains stationary.
• From 5 seconds to 8 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
• From 8 seconds to 10 seconds, he remains stationary.
• From 10 seconds to 11 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 7 meters.

The total distance traveled is 49 meters, so output 49.

Sample Input 2

6 3 2 9

Sample Output 2

36

During the 9 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 3 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
• From 3 seconds to 5 seconds, he remains stationary.
• From 5 seconds to 8 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
• From 8 seconds to 9 seconds, he remains stationary.

The total distance traveled is 36 meters, so output 36.

Sample Input 3

1 1 666 428

Sample Output 3

1

During the 428 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 1 second, he runs at a speed of 1 meter per second. The distance traveled during this time is 1 meter.
• From 1 second to 428 seconds, he remains stationary.

The total distance traveled is 1 meter, so output 1.

Problem Statement

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

Define the number of occurrences of a string t of length K as the number of integers i that satisfy the following condition:

• 1 \leq i \leq N-K+1
• The substring of S from the i-th character to the (i+K-1)-th character matches t.

Find the maximum value x of the number of occurrences of a string of length K. Also, output all strings of length K with x occurrences in ascending lexicographical order.

Constraints

• N, K are integers.
• S is a string of length N consisting of lowercase English letters.
• 1 \leq K \leq N \leq 100

Sample Input 1

9 3
ovowowovo

Sample Output 1

2
ovo owo

The following strings have two occurrences:

• For the string ovo, i=1,7 satisfy the condition, so the number of occurrences of ovo is 2.
• For the string owo, i=3,5 satisfy the condition, so the number of occurrences of owo is 2.

There is no string of length 3 with more than two occurrences, so the maximum value is 2.

On the other hand, the following are examples of strings with fewer than two occurrences:

• For the string vow, i=2 satisfies the condition, so the number of occurrences of vow is 1.
• For the string ooo, there is no i that satisfies the condition, so the number of occurrences of ooo is 0.

Sample Input 2

9 1
ovowowovo

Sample Output 2

5
o

Sample Input 3

35 3
thequickbrownfoxjumpsoverthelazydog

Sample Output 3

2
the

Problem Statement

A string T is called a good bracket sequence if and only if it satisfies the following condition:

• T can be made into an empty string by repeating the following operation zero or more times:

  • Choose () contained in T as a (contiguous) substring and remove it.

For example, (), (()()), and the empty string are good bracket sequences, but )()( and ))) are not good bracket sequences.

There is a string S. Initially, S is an empty string.
Process Q queries in the order they are given. After each query, determine whether S is a good bracket sequence.
There are two types of queries:

• 1 c: A character c is given. c is either ( or ). Append c to the end of S.
• 2: Remove the last character of S. It is guaranteed that S is not an empty string at this time.

Constraints

• 1 \leq Q \leq 8 \times 10^5
• c in queries of the first type is ( or ).
• It is guaranteed that S is not empty when a query of the second type is given.
• Q is an integer.

Sample Input 1

8
1 (
2
1 (
1 )
2
1 (
1 )
1 )

Sample Output 1

No
Yes
No
Yes
No
No
No
Yes

S immediately after processing the 1st query is (, which is not a good bracket sequence.
S immediately after processing the 2nd query is an empty string, which is a good bracket sequence.
S immediately after processing the 3rd query is (, which is not a good bracket sequence.
S immediately after processing the 4th query is (), which is a good bracket sequence.
S immediately after processing the 5th query is (, which is not a good bracket sequence.
S immediately after processing the 6th query is ((, which is not a good bracket sequence.
S immediately after processing the 7th query is ((), which is not a good bracket sequence.
S immediately after processing the 8th query is (()), which is a good bracket sequence.

Problem Statement

For positive integers x and y, define f(x,y) as follows:

• Let z be the string obtained by interpreting x,y in decimal notation as strings and concatenating them in this order. Let f(x,y) be the value when z is interpreted as an integer in decimal notation.

For example, f(3,14)=314,\ f(100,3)=1003.

You are given positive integers C and D. Find the number of integers x that satisfy the following conditions:

• 1 \leq x \leq D
• f(C, C+x) is a perfect square.

You are given T test cases, find the answer for each of them.

Constraints

• 1 \leq T \leq 3 \times 10^5
• 1 \leq C \leq 2 \times 10^8
• 1 \leq D \leq 5 \times 10^9
• All input values are integers.

Sample Input 1

4
4 80
183 5000
18 10
824 5000000000

Sample Output 1

3
2
0
1421

For the first test case, there are three values of x that satisfy the conditions: x = 5, 37, 80.

• When x=5, f(C, C+5) = f(4,9) = 49 = 7^2
• When x=37, f(C, C+37) = f(4,41) = 441 = 21^2
• When x=80, f(C, C+80) = f(4,84) = 484 = 22^2

For the second test case, there are two values of x that satisfy the conditions: x = 1, 3133.

• When x=1, f(C, C+1) = f(183,184) = 183184 = 428^2
• When x=3133, f(C, C+3133) = f(183,3316) = 1833316 = 1354^2

For the third test case, there are zero values of x that satisfy the conditions.

For the fourth test case, there are 1421 values of x that satisfy the conditions.

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.
Define the distance between vertices u and v as the number of edges in the path with endpoints at vertices u and v. (This path is uniquely determined.)

Solve the following problem for v = 1, 2, \dots, N.

• Among vertices 1, 2, \dots, N, output the number of the vertex that has the maximum distance from vertex v. If there are multiple vertices that satisfy the condition, output the vertex with the largest number.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \lt B_i \leq N
• The graph given in the input is a tree.
• All input values are integers.

Sample Input 1

3
1 2
2 3

Sample Output 1

3
3
1

The vertex with the maximum distance from vertex 1 is vertex 3.
The vertices with the maximum distance from vertex 2 are vertices 1 and 3. Among them, vertex 3, which has the larger number, is the answer.
The vertex with the maximum distance from vertex 3 is vertex 1.

Sample Input 2

5
1 2
2 3
2 4
1 5

Sample Output 2

4
5
5
5
4

Problem Statement

There are N intervals on a number line, numbered from 1 to N.

The left endpoint of interval i is at coordinate 0, and the right endpoint is at coordinate W_i. Here, W_1 < W_2 < \dots < W_N.

You are given Q queries; process them in the order they are given. Each query is one of the following three types:

• Type 1 (1 v): Let l be the coordinate of the current left endpoint of interval v. Translate each of the intervals numbered v or less so that its left endpoint is at coordinate l.
• Type 2 (2 v): Let r be the coordinate of the current right endpoint of interval v. Translate each of the intervals numbered v or less so that its right endpoint is at coordinate r.
• Type 3 (3 x): Output the current number of intervals that contain coordinate x+\frac{1}{2}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• W_1 < W_2 < \dots < W_N
• For v given in queries of types 1 and 2, 1 \leq v \leq N.
• For x given in queries of type 3, 0 \leq x \leq 10^9.
• At least one query of type 3 is given.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
1

Initially, the intervals in order of their numbers are [0, 2], [0, 4], [0, 6], [0, 10].

• For the 1st query, the coordinate of the right endpoint of interval 3 before the operation is 6, so the intervals after the operation are [4, 6], [2, 6], [0, 6], [0, 10] in order of their numbers.
• For the 2nd query, the coordinate of the left endpoint of interval 2 before the operation is 2, so the intervals after the operation are [2, 4], [2, 6], [0, 6], [0, 10] in order of their numbers.
• For the 3rd query, the intervals that contain coordinate 2 + \frac{1}{2} are intervals 1,2,3,4, which is four intervals, so output 4.
• For the 4th query, the coordinate of the right endpoint of interval 4 before the operation is 10, so the intervals after the operation are [8, 10], [6, 10], [4, 10], [0, 10] in order of their numbers.
• For the 5th query, the intervals that contain coordinate 1 + \frac{1}{2} is only interval 4, which is one interval, so output 1.

Problem Statement

There are N types of jewels numbered from 1 to N. You have an infinite number of jewels of all types. Jewels of the same type are indistinguishable.
Also, there is an integer U that is 2 or greater. The beauty of each jewel is represented by an integer value between 2 and U, inclusive, and the beauty of jewel i is b_i.

For each integer x satisfying 2 \leq x \leq U, let f(x) be the answer to the following problem:

You will arrange some jewels in a circular pattern to make a necklace.
Find the number, modulo 998244353, of necklaces such that the product of the beauties of the jewels used equals x.
Here, two necklaces are considered the same and counted only once if they match after rotation. However, two necklaces are counted separately if they do not match just by rotation, even if they match after flipping upside down and rotating. For example, consider the following:

• Necklace A: A necklace formed by arranging jewels 1, 2, 3 in this order clockwise.
• Necklace B: A necklace formed by arranging jewels 2, 3, 1 in this order clockwise.
• Necklace C: A necklace formed by arranging jewels 1, 3, 2 in this order clockwise.

Here, necklaces A and B are considered the same and counted only once, but necklaces A and C are counted separately.

Compute f(2), f(3), \dots, f(U).

Constraints

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

Sample Input 1

4 6
2 2 3 4

Sample Output 1

2 1 4 0 2

For example, when x=4, the following four necklaces satisfy the condition:

• A necklace formed by arranging jewels 1, 1 in this order clockwise.
• A necklace formed by arranging jewels 1, 2 in this order clockwise.
• A necklace formed by arranging jewels 2, 2 in this order clockwise.
• A necklace formed by arranging jewel 4.

Sample Input 2

4 16
2 2 2 2

Sample Output 2

4 0 10 0 0 0 24 0 0 0 0 0 0 0 70

Sample Input 3

14 12
10 2 2 3 8 7 11 6 12 4 9 5 3 2

Sample Output 3

3 2 7 1 7 1 15 4 4 1 24