Problem Statement

Find a length-N string that satisfies all of the following conditions:

• Each character is - or =.
• It is a palindrome.
• It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---

Problem Statement

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

How many different strings can be obtained by permuting the characters in S?

Constraints

• S is a string S of length 3 consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

3

By permuting the characters in S= aba, three different strings can be obtained: aab, aba, baa.

Sample Input 2

ccc

Sample Output 2

1

By permuting the characters in S= ccc, just one string can be obtained: ccc.

Sample Input 3

xyz

Sample Output 3

6

By permuting the characters in S= xyz, six different strings can be obtained: xyz, xzy, yxz, yzx, zxy, zyx.

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 100
• N and A_i are integers.
• S_i is L or R.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

• Initially, place the left hand on key 3 and the right hand on key 6.
• Press key 3 with the left hand.
• Press key 6 with the right hand.
• Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
• Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
• Press key 9 with the left hand.
• Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

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

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A,B\leq 10^9
• 1\leq D_1<D_2<\ldots<D_N\leq 10^9

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes

Problem Statement

For non-negative integers l and r (l < r), let S(l, r) denote the sequence (l, l+1, \ldots, r-2, r-1) formed by arranging integers from l through r-1 in order. Furthermore, a sequence is called a good sequence if and only if it can be represented as S(2^i j, 2^i (j+1)) using non-negative integers i and j.

You are given non-negative integers L and R (L < R). Divide the sequence S(L, R) into the fewest number of good sequences, and print that number of sequences and the division. More formally, find the minimum positive integer M for which there is a sequence of pairs of non-negative integers (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) that satisfies the following, and print such (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M).

• L = l_1 < r_1 = l_2 < r_2 = \cdots = l_M < r_M = R
• S(l_1, r_1), S(l_2, r_2), \ldots, S(l_M, r_M) are good sequences.

It can be shown that there is only one division that minimizes M.

Constraints

• 0 \leq L < R \leq 2^{60}
• All input values are integers.

Sample Input 1

3 19

Sample Output 1

5
3 4
4 8
8 16
16 18
18 19

S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) can be divided into the following five good sequences, which is the minimum possible number:

• S(3,4)=S(2^0\cdot 3,2^0\cdot4)=(3)
• S(4,8)=S(2^2\cdot 1,2^2\cdot 2)=(4,5,6,7)
• S(8,16)=S(2^3\cdot 1,2^3\cdot 2)=(8,9,10,11,12,13,14,15)
• S(16,18)=S(2^1\cdot 8,2^1\cdot 9)=(16,17)
• S(18,19)=S(2^0\cdot 18,2^0\cdot 19)=(18)

Sample Input 2

0 1024

Sample Output 2

1
0 1024

Sample Input 3

3940649673945088 11549545024454656

Sample Output 3

8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656

Problem Statement

You are given a tree with NK vertices. The vertices are numbered 1,2,\dots,NK, and the i-th edge (i=1,2,\dots,NK-1) connects vertices u_i and v_i bidirectionally.

Determine whether this tree can be decomposed into N paths, each of length K. More precisely, determine whether there exists an N \times K matrix P satisfying the following:

• P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K} is a permutation of 1,2,\dots,NK.
• For each i=1,2,\dots,N and j=1,2,\dots,K-1, there is an edge connecting vertices P_{i,j} and P_{i,j+1}.

Constraints

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

Sample Input 1

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

Sample Output 1

Yes

It can be decomposed into a path with vertices 1,2, a path with vertices 3,4, and a path with vertices 5,6.

Sample Input 2

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

Sample Output 2

No

Problem Statement

At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess.

There are N horses, numbered 1 to N. Horse i (1 \leq i \leq N) has a mood A_i and a tidiness B_i (where B_i is 1 or 2).

At night, the N horses bathe once each. Let p_j be the number of the horse that bathes in the j-th turn (1 \leq j \leq N). The satisfaction of horse p_j is given as follows:

• If j \geq 2, the product of the mood of horse p_j and the tidiness of horse p_{j-1}.
• If j = 1, the mood of horse p_j.

You will be given Q queries, one for each day over Q days. Process them in order. The query for the k-th day (1 \leq k \leq Q) is as follows:

• Change the mood of horse W_k to X_k and its tidiness to Y_k (where Y_k is 1 or 2). Then, find the maximum possible total satisfaction of the N horses' baths that night if you can decide the order in which the N horses bathe arbitrarily.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
• B_i is 1 or 2. (1 \leq i \leq N)
• 1 \leq W_k \leq N (1 \leq k \leq Q)
• 1 \leq X_k \leq 10^6 (1 \leq k \leq Q)
• Y_k is 1 or 2. (1 \leq k \leq Q)
• All input values are integers.

Sample Input 1

4 4
1 2
10 1
3 1
7 2
2 7 1
1 3 1
2 2 1
3 1000000 2

Sample Output 1

32
27
18
2000015

For the query on the first day, if the horses bathe in the order 3,1,4,2, the satisfaction of each horse is as follows:

• Horse 3's satisfaction is 3
• Horse 1's satisfaction is 1 \times 1 = 1
• Horse 4's satisfaction is 7 \times 2 = 14
• Horse 2's satisfaction is 7 \times 2 = 14

The total satisfaction in this case is 32.

For the query on the second day, if the horses bathe in the order 4,2,1,3, the satisfaction of each horse is as follows:

• Horse 4's satisfaction is 7
• Horse 2's satisfaction is 7 \times 2 = 14
• Horse 1's satisfaction is 3 \times 1 = 3
• Horse 3's satisfaction is 3 \times 1 = 3

The total satisfaction in this case is 27.

For the query on the third day, if the horses bathe in the order 4,3,2,1, the total satisfaction is 18.

For the query on the fourth day, if the horses bathe in the order 4,3,1,2, the total satisfaction is 2000015.

Sample Input 2

10 10
340019 2
598908 1
177330 2
575439 2
916653 2
451275 2
762769 2
36625 2
273231 2
367619 2
8 334230 2
8 835378 1
4 777076 2
6 61501 1
4 516395 1
4 35678 2
5 751493 1
3 815798 1
2 369777 2
5 941470 2

Sample Output 2

9417616
10146681
10549955
9708906
8847525
8463663
7860112
8606740
8516097
9236070