Problem Statement

You are given an odd-length string S consisting of lowercase English letters.

Print the central character of S.

Constraints

• S is an odd-length string consisting of lowercase English letters.
• The length of S is between 1 and 99 (inclusive).

Sample Input 1

atcoder

Sample Output 1

o

The central character of atcoder is o.

Sample Input 2

a

Sample Output 2

a

Problem Statement

Given N, print 2^N.

Constraints

• 0 \leq N \leq 30
• N is an integer.

Sample Input 1

3

Sample Output 1

8

We have 2^3=8.

Sample Input 2

30

Sample Output 2

1073741824

Problem Statement

Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 X: One person joins the end of the waiting line holding a ticket with menu number X.
• 2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.

Constraints

• 1 \leq Q \leq 100
• 1 \leq X \leq 100
• For each query of the second type, there is at least one person in the line before guiding.
• All input values are integers.

Sample Input 1

6
1 3
1 1
1 15
2
1 3
2

Sample Output 1

3
1

Initially, the waiting line is empty.

• For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
• For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
• For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
• For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
• For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
• For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.

Sample Input 2

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

Sample Output 2

Note that there may be no queries of the second type.

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

Constraints

• 1 \leq K \leq N \leq 100
• K and N are integers.
• S_i is a string of length 10 consisting of lowercase English letters.
• S_i \neq S_j if i \neq j.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc

Problem Statement

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

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

You are given a string S of length 2N. S contains exactly N occurrences of A and N occurrences of B.

Find the minimum number of operations (possibly zero) needed to make S have no adjacent identical characters, where an operation consists of swapping two adjacent characters in S.

Constraints

• 1\leq N \leq 5\times 10^5
• N is an integer.
• S is a string of length 2N consisting of N occurrences of A and N occurrences of B.

Sample Input 1

3
AABBBA

Sample Output 1

2

By performing operations as follows, you can achieve a state with no adjacent identical characters in two operations:

• Swap the 2nd and 3rd characters. S becomes ABABBA.
• Swap the 5th and 6th characters. S becomes ABABAB.

Sample Input 2

3
AAABBB

Sample Output 2

3

Note that you can only swap adjacent characters.

Sample Input 3

17
AAABABABBBABABBABABABABBAAABABABBA

Sample Output 3

15

Problem Statement

Takahashi has 10^{100} flower pots. Initially, he is not growing any plants.

You are given Q queries to process in order.

There are three types of queries as follows.

• 1: Prepare one empty flower pot and put a plant in it. Here, the plant's height is 0.
• 2 T: Wait for T days. During this time, the height of every existing plants increases by T.
• 3 H: Harvest all plants with a height of at least H, and output the number of plants harvested. The harvested plants are removed from their flower pots.

Assume that performing queries of the first and third types takes zero time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq T,H \leq 10^{9}
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

6
1
2 15
1
3 10
2 20
3 20

Sample Output 1

1
1

Queries are processed in the following order:

• In the first query, a plant of height 0 is planted.
• In the second query, the height of the plant increases to 15.
• In the third query, another plant of height 0 is planted. Now there is one plant of height 15 and one plant of height 0.
• In the fourth query, all plants with height at least 10 are harvested. Here, one plant of height 15 gets harvested, and one plant of height 0 remains. Since one plant was harvested, print 1 on the first line.
• In the fifth query, the height of the remaining plant increases to 20.
• In the sixth query, all plants with height at least 20 are harvested. Here, one plant of height 20 gets harvested. Thus, print 1 on the second line.

Sample Input 2

15
1
1
2 226069413
3 1
1
1
2 214168203
1
3 214168203
1
1
1
2 314506461
2 245642315
3 1

Sample Output 2

2
2
4

Problem Statement

Among integer pairs (x, y) satisfying 0 \leq x,y \leq M-1, how many are there such that the infinite sequence (s_1, s_2, \dots) defined by the following recurrence relation contains no multiples of M?

• s_1 = x
• s_2 = y
• s_n = A s_{n-1} + B s_{n-2} (n \geq 3)

Constraints

• 2 \leq M \leq 1000
• 0 \leq A, B \leq M-1
• All input values are integers.

Sample Input 1

4 1 2

Sample Output 1

7

The integer pairs satisfying the condition in the problem statement are (x,y) = (1,1), (1,3), (2,1), (2,2), (2,3), (3,1), (3,3), for a total of seven pairs.

For example, when (x,y) = (2,1), the corresponding sequence is (2,1,5,7,17,31,65,127,\dots). This sequence contains no multiples of 4. Thus, (x,y) = (2,1) satisfies the condition in the problem statement.

On the other hand, when (x,y) = (3,2), the corresponding sequence is (3,2,8,12,28,52,108,212,\dots). The third term of this sequence is 8, which is a multiple of 4. Thus, (x,y) = (3,2) does not satisfy the condition in the problem statement.

Sample Input 2

446 1 1

Sample Output 2

0

No integer pairs satisfy the condition in the problem statement.

Sample Input 3

1000 784 385

Sample Output 3

995373

Problem Statement

Takahashi plans to participate in N AtCoder contests.

In the i-th contest (1 \leq i \leq N), if his rating is between L_i and R_i (inclusive), his rating increases by 1.

You are given Q queries in the following format:

• An integer X is given. Assuming that Takahashi's initial rating is X, determine his rating after participating in all N contests.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N)
• 1 \leq Q \leq 3 \times 10^5
• For each query, 1 \leq X \leq 5 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

6
6
8

For the 1st query, the rating changes as follows:

• In the 1st contest, the rating is between 1 and 5, so it increases by 1, becoming 4.
• In the 2nd contest, the rating is not between 1 and 3, so it remains 4.
• In the 3rd contest, the rating is between 3 and 6, so it increases by 1, becoming 5.
• In the 4th contest, the rating is not between 2 and 4, so it remains 5.
• In the 5th contest, the rating is between 4 and 7, so it increases by 1, becoming 6.

For the 2nd query, the rating increases in the 1st, 2nd, 3rd, and 5th contests, ending at 6.

For the 3rd query, the rating increases in the 1st, 3rd, and 5th contests, ending at 8.

Sample Input 2

10
1 1999
1 1999
1200 2399
1 1999
1 1999
1 1999
2000 500000
1 1999
1 1999
1600 2799
7
1
1995
2000
2399
500000
2799
1000

Sample Output 2

8
2002
2003
2402
500001
2800
1007

Sample Input 3

15
260522 414575
436426 479445
148772 190081
190629 433447
47202 203497
394325 407775
304784 463982
302156 468417
131932 235902
78537 395728
223857 330739
286918 329211
39679 238506
63340 186568
160016 361868
10
287940
296263
224593
101449
336991
390310
323355
177068
11431
8580

Sample Output 3

287946
296269
224599
101453
336997
390315
323363
177075
11431
8580