Problem Statement

Does 2^n \gt n^2 hold?

Constraints

• n is an integer between 1 and 10^9 (inclusive).

Sample Input 1

5

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence A of length N, according to the following procedure.

• First, make a cut from the center in the 12 o'clock direction.
• Next, do N operations. The i-th operation is as follows.
  • Rotate the pizza A_i degrees clockwise.
  • Then, make a cut from the center in the 12 o'clock direction.

For example, if A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

• All values in input are integers.
• 1 \le N \le 359
• 1 \le A_i \le 359
• There will be no multiple cuts at the same position.

Sample Input 1

4
90 180 45 195

Sample Output 1

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120 degrees.

Sample Input 2

1
1

Sample Output 2

359

Sample Input 3

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3

170

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

• N is an integer.
• 1 \le N < 10^{18}

Sample Input 1

16

Sample Output 1

73

• For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
  • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
• For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
  • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.

Problem Statement

Solve the following problem for T test cases.

Given are non-negative integers a and s. Is there a pair of non-negative integers (x,y) that satisfies both of the conditions below?

• x\ \text{AND}\ y=a
• x+y=s

Constraints

• 1 \leq T \leq 10^5
• 0 \leq a,s \lt 2^{60}
• All values in input are integers.

Sample Input 1

2
1 8
4 2

Sample Output 1

Yes
No

In the first test case, some pairs such as (x,y)=(3,5) satisfy the conditions.

In the second test case, no pair of non-negative integers satisfies the conditions.

Sample Input 2

4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

Sample Output 2

No
Yes
Yes
No

Problem Statement

Takahashi has a secret integer sequence a. You know that the length of a is N.

You want to guess the contents of a. He has promised to give you the following Q additional pieces of information.

• The i-th information: the value a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}.

Is it possible to determine the sum of all elements in a, a_1+a_2+\cdots+a_N, if the Q pieces of promised information are given?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq \min(2 \times 10^5,\frac{N(N+1)}{2})
• 1 \leq l_i \leq r_i \leq N
• (l_i,r_i) \neq (l_j,r_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3 3
1 2
2 3
2 2

Sample Output 1

Yes

From the first and second information, we can find the value a_1+a_2+a_2+a_3. By subtracting the value of a_2 from it, we can determine the value a_1+a_2+a_3.

Sample Input 2

4 3
1 3
1 2
2 3

Sample Output 2

No

We can determine the sum of the first 3 elements of a, but not the sum of all elements.

Sample Input 3

4 4
1 1
2 2
3 3
1 4

Sample Output 3

Yes

The fourth information directly gives us the sum of all elements.

Problem Statement

In the Kingdom of Takahashi, N citizens numbered 1 to N took an examination of competitive programming.
There were two tests, and Citizen i ranked P_i-th in the first test and Q_i-th in the second test.
There were no ties in either test. That is, each of the sequences P and Q is a permutation of (1, 2, ..., N).

Iroha, the president of the kingdom, is going to select K citizens for the national team at the coming world championship of competitive programming.
The members of the national team must be selected so that the following is satisfied.

• There should not be a pair of citizens (x, y) where Citizen x is selected and Citizen y is not selected such that P_x > P_y and Q_x > Q_y.
  • In other words, if Citizen y got a rank smaller than that of Citizen x in both tests, it is not allowed to select Citizen x while not selecting Citizen y.

To begin with, Iroha wants to know the number of ways to select citizens for the national team that satisfy the condition above. Find it to help her.
Since this number can be enormous, print it modulo 998244353.

Constraints

• All values in input are integers.
• 1 \le N \le 300
• 1 \le K \le N
• Each of P and Q is a permutation of (1,2,...,N).

Sample Input 1

4 2
2 4 3 1
2 1 4 3

Sample Output 1

3

• It is fine to select Citizen 1 and Citizen 2 for the team.
• If Citizen 1 and Citizen 3 are selected, Citizen 4 ranked higher than Citizen 3 did in both tests, so the pair (x,y)=(3,4) would violate the condition in the Problem Statement.
• It is fine to select Citizen 1 and Citizen 4.
• If Citizen 2 and Citizen 3 are selected, the pair (x,y)=(3,1) would violate the condition.
• It is fine to select Citizen 2 and Citizen 4.
• If Citizen 3 and Citizen 4 are selected, the pair (x,y)=(3,1) would violate the condition.

The final answer is 3.

Sample Input 2

33 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Sample Output 2

168558757

All \binom{33}{16} = 1166803110 ways of selecting 16 from the 33 citizens satisfy the requirement.
Therefore, we should print 1166803110 modulo 998244353, that is, 168558757.

Sample Input 3

15 7
4 9 7 5 6 13 2 11 3 1 12 14 15 10 8
4 14 9 12 7 15 1 2 8 11 3 5 13 6 10

Sample Output 3

23

Problem Statement

Given a sequence A of N numbers, answer the following Q questions.

• In the i-th question, you are given integers L_i and R_i. Is A_{L_i} \times A_{L_i+1} \times \dots \times A_{R_i} a cubic number?

Here, a positive integer x is said to be a cubic number when there is a positive integer y such that x=y^3.

Constraints

• All values in input are integers.
• 1 \le N,Q \le 2 \times 10^5
• 1 \le A_i \le 10^6
• 1 \le L_i \le R_i \le N

Sample Input 1

8 5
7 49 30 1 15 8 6 10
1 2
2 3
4 4
5 8
3 8

Sample Output 1

Yes
No
Yes
No
Yes

• For the first question, 7 \times 49 = 343 is a cubic number.
• For the second question, 49 \times 30 = 1470 is not a cubic number.
• For the third question, 1 is a cubic number.
• For the fourth question, 15 \times 8 \times 6 \times 10 = 7200 is not a cubic number.
• For the fifth question, 30 \times 1 \times 15 \times 8 \times 6 \times 10 = 216000 is a cubic number.

Problem Statement

N people numbered 1 to N are standing in a circle, in the clockwise order of Person 1, Person 2, \cdots, Person N. The direction each person faces is given by a string S of length N. For each i (1 \leq i \leq N), Person i is facing in the counter-clockwise direction if S_i = L, and clockwise direction if S_i = R.

The following operation will be repeated N-1 times.

• Choose one of the remaining people with equal probability, and remove from the circle the nearest person seen from the chosen person. This incurs a cost equal to the distance from the chosen person to the removed person.

Here, the distance from Person i to Person j (i \neq j) is defined as follows.

1. When Person i is facing in the clockwise direction:
   • j-i if i \lt j;
   • j-i+N if i \gt j.
2. When Person i is facing in the counter-clockwise direction:
   • i-j+N if i \lt j;
   • i-j if i \gt j.

Find the expected value of the total cost incurred, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \leq N \leq 300
• N is an integer.
• S is a string of length N consisting of L and R.

Sample Input 1

3
LLR

Sample Output 1

831870297

The sought expected value is \frac{17}{6}. We have 831870297 \times 6 \equiv 17\pmod{998244353}, so 831870297 should be printed.

For your reference, here is one possible scenario.

1. Person 2 is chosen. The nearest person seen from Person 2 remaining in the circle is Person 1, who gets removed from the circle.
2. Person 2 is chosen again. The nearest person seen from Person 2 remaining in the circle is Person 3, who gets removed from the circle.

In this case, the total cost incurred is 3(=1+2).

Sample Input 2

10
RRRRRRLLRR

Sample Output 2

460301586