Problem Statement

You are given a string S consisting of lowercase English characters. The length of S is between 1 and 3, inclusive.

Print the string of length 6 that is a repetition of S.

It can be shown that there uniquely exists such a string under the Constraints of this problem.

Constraints

• S is a string consisting of lowercase English characters of length between 1 and 3, inclusive.

Sample Input 1

abc

Sample Output 1

abcabc

These are strings that are repetitions of S = abc: abc, abcabc, abcabcabc, abcabcabcabc, and so on. Among them, abcabc has the length of 6, so abcabc should be printed.

Sample Input 2

zz

Sample Output 2

zzzzzz

Problem Statement

You are given an N-character string S consisting of lowercase English letters.

Output the string of N-A-B characters obtained by removing the first A characters and the last B characters from S.

Constraints

• 1\le N\le20
• 0\le A
• 0\le B
• A+B\lt N
• S is a string of N characters consisting of lowercase English letters.
• N, A, and B are all integers.

Sample Input 1

7 1 3
atcoder

Sample Output 1

tco

Removing the first one character and the last three characters from atcoder gives tco.

Sample Input 2

1 0 0
a

Sample Output 2

a

The string to be output may be equal to S.

Sample Input 3

20 4 8
abcdefghijklmnopqrst

Sample Output 3

efghijkl

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq D \leq 100
• N and D are integers.
• S_i is a string of length D consisting of o and x.

Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.

Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)

Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.

Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5

Problem Statement

There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days. On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it. If no such noodle is available on any day, his plan fails. Additionally, he cannot eat the same noodle on multiple days.

Can Takahashi accomplish his meal plan?

Constraints

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

Sample Input 1

3 2
1 1 3
3 1

Sample Output 1

Yes

He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.

Sample Input 2

1 1
1000000000
1

Sample Output 2

No

A noodle of length exactly 1 is needed.

Sample Input 3

5 2
1 2 3 4 5
5 5

Sample Output 3

No

Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.

Problem Statement

The problem statement of Problem C is the same as Problem E. Only the constraint shown in red differ.

You are given integer sequences A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_{N-1}) consisting of integers between 0 and M-1, inclusive. The lengths of A and B are N and N-1, respectively.
You can perform the following operation on A any number of times.

• Choose an integer i with 1 \leq i \leq N, and add 1 to A_i.

Find the minimum number of operations required to satisfy the following condition.
It can be proved that the condition can always be satisfied under the constraints of this problem.

• For i=1,2,\dots,N-1, the remainder when A_i+A_{i+1} is divided by M equals B_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• M=2
• 0 \leq A_i \leq M-1
• 0 \leq B_i \leq M-1
• All input values are integers.

Sample Input 1

3 2
1 1 1
1 1

Sample Output 1

1

If we choose i=2 for the first operation, we get A=(1,2,1).
Since A_1+A_2=1+2=3 and A_2+A_3=2+1=3, the condition is satisfied.
A=(1,1,1) does not satisfy the condition, so the answer is 1.

Sample Input 2

2 2
1 1
0

Sample Output 2

0

Sample Input 3

10 2
0 0 0 1 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0

Sample Output 3

4

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

• Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

Constraints

• S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
• The lengths of S and T are equal.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

• Change S to acbe and append acbe to the end of X.

• Change S to acbc and append acbc to the end of X.

• Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Problem Statement

There is a sequence that contains one 0, A=(0).
Additionally, you are given a string of length N, S=s_1s_2\ldots s_N, consisting of L and R.

For each i=1, 2, \ldots, N in this order, the following will be done.

• If s_i is L, insert i to the immediate left of i-1 in A.
• If s_i is R, insert i to the immediate right of i-1 in A.

Find the final contents of A.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• |S| = N
• s_i is L or R.

Sample Input 1

5
LRRLR

Sample Output 1

1 2 4 5 3 0

Initially, A=(0).
S_1 is L, which makes it A=(1,0).
S_2 is R, which makes it A=(1,2,0).
S_3 is R, which makes it A=(1,2,3,0).
S_4 is L, which makes it A=(1,2,4,3,0).
S_5 is R, which makes it A=(1,2,4,5,3,0).

Sample Input 2

7
LLLLLLL

Sample Output 2

7 6 5 4 3 2 1 0

Problem Statement

There is a tree with N vertices numbered 1 to N. For each i\ (2 \leq i \leq N), there is an edge connecting vertex i and vertex \lfloor \frac{i}{2} \rfloor. There are no other edges.

In this tree, find the number of vertices whose distance from vertex X is K. Here, the distance between two vertices u and v is defined as the number of edges in the simple path connecting vertices u and v.

You have T test cases to solve.

Constraints

• 1\leq T \leq 10^5
• 1\leq N \leq 10^{18}
• 1\leq X \leq N
• 0\leq K \leq N-1
• All input values are integers.

Sample Input 1

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

Sample Output 1

1
3
4
2
0

The tree for N=10 is shown in the following figure.

Here,

• There is 1 vertex, 2, whose distance from vertex 2 is 0.
• There are 3 vertices, 1,4,5, whose distance from vertex 2 is 1.
• There are 4 vertices, 3,8,9,10, whose distance from vertex 2 is 2.
• There are 2 vertices, 6,7, whose distance from vertex 2 is 3.
• There are no vertices whose distance from vertex 2 is 4.

Sample Input 2

10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

Sample Output 2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

Problem Statement

AtCoder Inc.'s online shop currently handles N products, and the stock of product i is A_i units remaining.

Process the following Q orders in order. The i-th order is as follows:

• Buy k_i units each of products l_i,l_i+1,\dots,r_i. For products with fewer than k_i units, buy all available units. Report the total number of products bought in this order.

Note that for i<Q, the stock of products bought in the i-th order is reduced before proceeding to the (i+1)-th order.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^{15}
• 1 \le Q \le 3 \times 10^5
• 1 \le l_i \le r_i \le N
• 1 \le k_i \le 10^9

Sample Input 1

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

Sample Output 1

6
11
0
2
10

This input contains 5 orders.

• Initially, the stocks of the products are (from product 1 onward) 2,6,4,5,7,5 units.
• The first order is l_1 = 1, r_1 = 6, k_1 = 1.
  • In this order, 1,1,1,1,1,1 units of the products are bought, for a total of 6 units.
  • After this, the stocks of the products become 1,5,3,4,6,4 units.
• The second order is l_2 = 3, r_2 = 5, k_2 = 4.
  • In this order, 0,0,3,4,4,0 units of the products are bought, for a total of 11 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The third order is l_3 = 4, r_3 = 4, k_3 = 1.
  • In this order, 0,0,0,0,0,0 units of the products are bought, for a total of 0 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The fourth order is l_4 = 2, r_4 = 5, k_4 = 1.
  • In this order, 0,1,0,0,1,0 units of the products are bought, for a total of 2 units.
  • After this, the stocks of the products become 1,4,0,0,1,4 units.
• The fifth order is l_5 = 1, r_5 = 6, k_5 = 100.
  • In this order, 1,4,0,0,1,4 units of the products are bought, for a total of 10 units.
  • After this, the stocks of the products become 0,0,0,0,0,0 units.