Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

• 1 \leq N \leq 100
• All inputs are integers.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox

Problem Statement

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

Determine whether it is possible to rearrange the characters in S to make it match the string ABC.

Constraints

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

Sample Input 1

BAC

Sample Output 1

Yes

You can make S match ABC by swapping the first and second characters of S.

Sample Input 2

AAC

Sample Output 2

No

You cannot make S match ABC no matter how you rearrange the characters.

Sample Input 3

ABC

Sample Output 3

Yes

Sample Input 4

ARC

Sample Output 4

No

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

• If there is a tooth in hole T_i, remove the tooth from hole T_i.
• If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

• All input values are integers.
• 1 \le N, Q \le 1000
• 1 \le T_i \le N

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

28

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

• In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
• In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
• In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
• In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
• In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
• In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

5

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

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

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

There is an empty integer sequence A=(). You are given Q queries, and you need to process them in the given order. There are two types of queries:

• Type 1: Given in the format 1 c x. Add c copies of x to the end of A.
• Type 2: Given in the format 2 k. Remove the first k elements from A and output the sum of the removed k integers. It is guaranteed that k is at most the length of A at that time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• In type 1 queries, 1 \leq c \leq 10^{9}.
• In type 1 queries, 1 \leq x \leq 10^{9}.
• In type 2 queries, letting n be the length of A at that time, 1 \leq k \leq \min(10^{9},n).
• All input values are integers.

Sample Input 1

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

Sample Output 1

11
19

• 1st query: Add 2 copies of 3 to the end of A. Then, A=(3,3).
• 2nd query: Add 4 copies of 5 to the end of A. Then, A=(3,3,5,5,5,5).
• 3rd query: Remove the first 3 elements from A. Then, the sum of the removed 3 integers is 3+3+5=11, so output 11. After removal, A=(5,5,5).
• 4th query: Add 6 copies of 2 to the end of A. Then, A=(5,5,5,2,2,2,2,2,2).
• 5th query: Remove the first 5 elements from A. Then, the sum of the removed 5 integers is 5+5+5+2+2=19, so output 19. After removal, A=(2,2,2,2).

Sample Input 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

Sample Output 2

990
804
3024

Sample Input 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

Sample Output 3

16430766442004320
155640513381884866
149721462357295680

Problem Statement

Find the number of positive integers not greater than N that have exactly 9 positive divisors.

Constraints

• 1 \leq N \leq 4 \times 10^{12}
• All input values are integers.

Sample Input 1

200

Sample Output 1

3

Three positive integers 36,100,196 satisfy the condition.

Sample Input 2

4000000000000

Sample Output 2

407073

Problem Statement

You are given positive integers N and K.
Find the sum, modulo 998244353, of all positive integers x that do not exceed N and satisfy the following condition:

• the popcount of x is exactly K.

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 100
• 1 \leq N < 2^{60}
• 1 \leq K \leq 60
• T, N, and K are integers.

Sample Input 1

2
20 2
1234567890 17

Sample Output 1

100
382730918

For the first test case, there are nine positive integers not exceeding 20 whose popcount is 2: 3, 5, 6, 9, 10, 12, 17, 18, 20. Their sum is 100.
The remainder when 100 is divided by 998244353 is 100, so output 100 on the first line.
Remember to output the sum modulo 998244353.

Problem Statement

Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.

• First, take a positive divisor M of N that is not equal to N.
• Next, decide the attendance for the first M days.
• Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.

Note that different values of M may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.

Constraints

• N is an integer between 2 and 10^5, inclusive.
• S is a string of length N consisting of # and ..

Sample Input 1

6
##.#.#

Sample Output 1

3

Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.

Sample Input 2

7
...####

Sample Output 2

1

Sample Input 3

12
####.####.##

Sample Output 3

19