Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

• At least one interviewer's evaluation is Good.
• No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

• 1 \leq N \leq 100
• S is a string of length N consisting of o, -, and x.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.

Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

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

Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.

Sample Input 2

1

Sample Output 2

Long

Problem Statement

You are given a positive integer N. If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.

Constraints

• 1\leq N\leq10^{18}
• N is an integer.

Sample Input 1

324

Sample Output 1

Yes

For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied. Thus, you should print Yes.

Sample Input 2

5

Sample Output 2

No

There are no integers x and y such that 2^x3^y=5. Thus, you should print No.

Sample Input 3

32

Sample Output 3

Yes

For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.

Sample Input 4

37748736

Sample Output 4

Yes

Problem Statement

You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.

Constraints

• S consists of lowercase English letters.
• 1 \le |S| \le 10^5 (|S| is the length of S.)
• L and R are integers.
• 1 \le L \le R \le |S|

Sample Input 1

3 7
abcdefgh

Sample Output 1

abgfedch

After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.

Sample Input 2

1 7
reviver

Sample Output 2

reviver

The operation may result in the same string as the original.

Sample Input 3

4 13
merrychristmas

Sample Output 3

meramtsirhcyrs

Problem Statement

A single-player card game is popular in AtCoder Inc. Each card in the game has a lowercase English letter or the symbol @ written on it. There is plenty number of cards for each kind. The game goes as follows.

1. Arrange the same number of cards in two rows.
2. Replace each card with @ with one of the following cards: a, t, c, o, d, e, r.
3. If the two rows of cards coincide, you win. Otherwise, you lose.

To win this game, you will do the following cheat.

• Freely rearrange the cards within a row whenever you want after step 1.

You are given two strings S and T, representing the two rows you have after step 1. Determine whether it is possible to win with cheating allowed.

Constraints

• S and T consist of lowercase English letters and @.
• The lengths of S and T are equal and between 1 and 2\times 10^5, inclusive.

Sample Input 1

ch@ku@ai
choku@@i

Sample Output 1

Yes

You can replace the @s so that both rows become chokudai.

Sample Input 2

ch@kud@i
akidu@ho

Sample Output 2

Yes

You can cheat and replace the @s so that both rows become chokudai.

Sample Input 3

aoki
@ok@

Sample Output 3

No

You cannot win even with cheating.

Sample Input 4

aa
bb

Sample Output 4

No

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

Problem Statement

We have a horizontal cylinder. Given Q queries, process them in the given order.
Each query is of one of the following two types.

• 1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.
• 2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.

We assume that the balls do never change their order in the cylinder.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq 10^9
• Whenever a query of type 2 c is given, there are c or more balls in the cylinder.
• All values in input are integers.

Sample Input 1

4
1 2 3
2 2
1 3 4
2 3

Sample Output 1

4
8

• For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,2,2) written on them, from left to right.
• For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed. The cylinder has now a ball with a number (2) written on it, from left to right.
• For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right.
• For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed. The cylinder has now balls with numbers (3,3) written on them, from left to right.

Sample Input 2

2
1 1000000000 1000000000
2 1000000000

Sample Output 2

1000000000000000000

Sample Input 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 3

There may be nothing you should print.

Problem Statement

You are given a string S of length N consisting of 0 and 1. It describes a length-N sequence A=(A _ 1,A _ 2,\ldots,A _ N). If the i-th character of S (1\leq i\leq N) is 0, then A _ i=0; if it is 1, then A _ i=1.

Find the following:

\[\sum _ {1\leq i\leq j\leq N}(\cdots((A _ i\barwedge A _ {i+1})\barwedge A _ {i+2})\barwedge\cdots\barwedge A _ j)\]

More formally, find \displaystyle\sum _ {i=1} ^ {N}\sum _ {j=i} ^ Nf(i,j) for f(i,j)\ (1\leq i\leq j\leq N) defined as follows:

\[f(i,j)=\left\{\begin{matrix} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right.\]

Here, \barwedge, NAND, is a binary operator satisfying the following:

\[0\barwedge0=1,0\barwedge1=1,1\barwedge0=1,1\barwedge1=0.\]

Constraints

• 1\leq N\leq10^6
• S is a string of length N consisting of 0 and 1.
• All input values are integers.

Sample Input 1

5
00110

Sample Output 1

9

Here are the values of f(i,j) for the pairs (i,j) such that 1\leq i\leq j\leq N:

• f(1,1)=0=0
• f(1,2)=0\barwedge0=1
• f(1,3)=(0\barwedge0)\barwedge1=0
• f(1,4)=((0\barwedge0)\barwedge1)\barwedge1=1
• f(1,5)=(((0\barwedge0)\barwedge1)\barwedge1)\barwedge0=1
• f(2,2)=0=0
• f(2,3)=0\barwedge1=1
• f(2,4)=(0\barwedge1)\barwedge1=0
• f(2,5)=((0\barwedge1)\barwedge1)\barwedge0=1
• f(3,3)=1=1
• f(3,4)=1\barwedge1=0
• f(3,5)=(1\barwedge1)\barwedge0=1
• f(4,4)=1=1
• f(4,5)=1\barwedge0=1
• f(5,5)=0=0

Their sum is 0+1+0+1+1+0+1+0+1+1+0+1+1+1+0=9, so print 9.

Note that \barwedge does not satisfy the associative property. For instance, (1\barwedge1)\barwedge0=0\barwedge0=1\neq0=1\barwedge1=1\barwedge(1\barwedge0).

Sample Input 2

30
101010000100101011010011000010

Sample Output 2

326

Problem Statement

We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.

Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.

Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.

Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.

Find the minimum cost needed to distribute loaves to all children.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i\leq 10^9
• A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
• All values in input are integers.

Sample Input 1

5 7
1 2 1 2 1

Sample Output 1

16

Takahashi can cut the loaf for the children as follows.

• Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
• Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
• Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
• Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.

This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.

Sample Input 2

3 1000000000000000
1000000000 1000000000 1000000000

Sample Output 2

1000005000000000

Note that each child i must receive a loaf of length exactly A_i.