Problem Statement

Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)

Is it possible that the total amount of money in the purse is X yen?

Constraints

• 0 \leq X \leq 1000
• All values in input are integers.

Sample Input 1

500

Sample Output 1

Yes

If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.

Sample Input 2

40

Sample Output 2

No

Sample Input 3

0

Sample Output 3

No

Note that the purse has at least one 100-yen coin.

Problem Statement

On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.

For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.

You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.

Constraints

• S consists of lowercase English letters.
• The length of S is between 1 and 1000 (inclusive).

Sample Input 1

aaba

Sample Output 1

aaab
baaa

By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.

Sample Input 2

z

Sample Output 2

z
z

Any sequence of operations results in z.

Sample Input 3

abracadabra

Sample Output 3

aabracadabr
racadabraab

Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 1000
• All values in input are integers.

Sample Input 1

3
1 1
2 1
3 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

3
1 3
2 2
3 1

Sample Output 2

3.833333333333333

Sample Input 3

5
3 9
1 2
4 6
1 5
5 3

Sample Output 3

8.916666666666668

Problem Statement

Among the sequences P that are permutations of (1, 2, \dots, N) and satisfy the condition below, find the lexicographically smallest sequence.

• For each i = 1, \dots, M, A_i appears earlier than B_i in P.

If there is no such P, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• All values in input are integers.

Sample Input 1

4 3
2 1
3 4
2 4

Sample Output 1

2 1 3 4

The following five permutations P satisfy the condition: (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1). The lexicographically smallest among them is (2, 1, 3, 4).

Sample Input 2

2 3
1 2
1 2
2 1

Sample Output 2

-1

No permutations P satisfy the condition.

Problem Statement

For positive integers X and Y, a rectangle in a two-dimensional plane that satisfies the conditions below is said to be good.

• Every edge is parallel to the x- or y-axis.
• For every vertex, its x-coordinate is an integer between 0 and X (inclusive), and y-coordinate is an integer between 0 and Y (inclusive).

Determine whether it is possible to place the following three good rectangles without overlapping: a good rectangle of an area at least A, another of an area at least B, and another of an area at least C.

Here, three rectangles are considered to be non-overlapping when the intersection of any two of them has an area of 0.

Constraints

• 1 \leq X, Y \leq 10^9
• 1 \leq A, B, C \leq 10^{18}
• All values in input are integers.

Sample Input 1

3 3 2 2 3

Sample Output 1

Yes

The figure below shows a possible placement, where the number in a rectangle represents its area.

We can see that 2 \geq A, 3 \geq B, 3 \geq C, satisfying the conditions.

Sample Input 2

3 3 4 4 1

Sample Output 2

No

There is no possible placement under the conditions.

Sample Input 3

1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

No

Problem Statement

Let us define a correct parenthesis sequence as a string that satisfies one of the following conditions.

• It is an empty string.
• It is a concatenation of (, A, ), in this order, for some correct parenthesis sequence A.
• It is a concatenation of A, B, in this order, for some correct parenthesis sequences A and B.

We have a string S of length N consisting of ( and ).

Given Q queries \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q, process them in order. There are two kinds of queries, with the following formats and content.

• 1 l r: Swap the l-th and r-th characters of S.
• 2 l r: Determine whether the contiguous substring from the l-th through the r-th character is a correct parenthesis sequence.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• S is a string of length N consisting of ( and ).
• 1 \leq l < r \leq N
• N,Q,l,r are all integers.
• Each query is in the format 1 l r or 2 l r.
• There is at least one query in the format 2 l r.

Sample Input 1

5 3
(())(
2 1 4
2 1 2
2 4 5

Sample Output 1

Yes
No
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, (( is not a correct parenthesis sequence.

In the third query, )( is not a correct parenthesis sequence.

Sample Input 2

5 3
(())(
2 1 4
1 1 4
2 1 4

Sample Output 2

Yes
No

In the first query, (()) is a correct parenthesis sequence.

In the second query, S becomes )()((.

In the third query, )()( is not a correct parenthesis sequence.

Sample Input 3

8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

Sample Output 3

Yes
No
No

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1,2,\ldots,N, and the i-th edge (1 \leq i \leq N-1) connects Vertex u_i and Vertex v_i.

Find the number of integers i (1 \leq i \leq N) that satisfy the following condition.

• The size of the maximum matching of the graph obtained by deleting Vertex i and all incident edges from the tree is equal to the size of the maximum matching of the original tree.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2
2 3

Sample Output 1

2

The size of the maximum matching of the original tree is 1.

The size of the maximum matching of the graph obtained by deleting Vertex 1 and all incident edges from the tree is 1.

The size of the maximum matching of the graph obtained by deleting Vertex 2 and all incident edges from the tree is 0.

The size of the maximum matching of the graph obtained by deleting Vertex 3 and all incident edges from the tree is 1.

Thus, two integers i=1,3 satisfy the condition, so we should print 2.

Sample Input 2

2
1 2

Sample Output 2

0

Sample Input 3

6
2 5
3 5
1 4
4 5
4 6

Sample Output 3

4

Problem Statement

Given is a sequence of N positive integers A = (A_1, \dots, A_N).

Process Q queries. In the i-th query (1 \leq i \leq Q), determine whether it is possible to choose one or more elements from A_{L_i}, A_{L_i + 1}, \dots, A_{R_i} so that their \mathrm{XOR} is X_i.

Constraints

• 1 \leq N \leq 4 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \lt 2^{60}
• 1 \leq L_i \leq R_i \leq N
• 1 \leq X_i \lt 2^{60}
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
No

In the first query, you can choose A_1 and A_3, whose \mathrm{XOR} is 7.

In the second query, there is no way to choose elements so that their \mathrm{XOR} is 7.

Sample Input 2

10 10
8 45 56 9 38 28 33 5 15 19
10 10 53
3 8 60
1 10 29
5 7 62
3 7 51
8 8 52
1 4 60
6 8 32
4 8 58
5 9 2

Sample Output 2

No
No
Yes
No
Yes
No
No
No
Yes
Yes