Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

• All input values are integers.
• 1 \leq L \leq R \leq N \leq 100

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

Problem Statement

Takahashi is health-conscious and concerned about whether he is getting enough of M types of nutrients from his diet.

For the i-th nutrient, his goal is to take at least A_i units per day.

Today, he ate N foods, and from the i-th food, he took X_{i,j} units of nutrient j.

Determine whether he has met the goal for all M types of nutrients.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 0 \leq A_i, X_{i,j} \leq 10^7
• All input values are integers.

Sample Input 1

2 3
10 20 30
20 0 10
0 100 100

Sample Output 1

Yes

For nutrient 1, Takahashi took 20 units from the 1-st food and 0 units from the 2-nd food, totaling 20 units, thus meeting the goal of taking at least 10 units.
Similarly, he meets the goal for nutrients 2 and 3.

Sample Input 2

2 4
10 20 30 40
20 0 10 30
0 100 100 0

Sample Output 2

No

The goal is not met for nutrient 4.

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

• You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
• The test result is represented by a single English letter R_i.
  • R_i = o means that Door X opened in the i-th test.
  • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

• N, M, K, C_i, and A_{i,j} are integers.
• 1 \le K \le N \le 15
• 1 \le M \le 100
• 1 \le C_i \le N
• 1 \le A_{i,j} \le N
• A_{i,j} \neq A_{i,k} if j \neq k.
• R_i is o or x.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

• In the first test, keys 1, 2, 3 were used, and Door X opened.
• In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

• Key 1 is real, key 2 is a dummy, and key 3 is real.
• Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8

Problem Statement

Given integers N and M, compute the sum \displaystyle \sum_{k=0}^{N} \rm{popcount}(k \mathbin{\&} M), modulo 998244353.

Here, \mathbin{\&} represents the bitwise \rm{AND} operation.

Constraints

• N is an integer between 0 and 2^{60} - 1, inclusive.
• M is an integer between 0 and 2^{60} - 1, inclusive.

Sample Input 1

4 3

Sample Output 1

4

• \rm{popcount}(0\mathbin{\&}3) = 0
• \rm{popcount}(1\mathbin{\&}3) = 1
• \rm{popcount}(2\mathbin{\&}3) = 1
• \rm{popcount}(3\mathbin{\&}3) = 2
• \rm{popcount}(4\mathbin{\&}3) = 0

The sum of these values is 4.

Sample Input 2

0 0

Sample Output 2

0

It is possible that N = 0 or M = 0.

Sample Input 3

1152921504606846975 1152921504606846975

Sample Output 3

499791890

Remember to compute the result modulo 998244353.

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

Find \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor.

Here, \lfloor x \rfloor represents the greatest integer not greater than x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 2 \rfloor=2.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

3
3 1 4

Sample Output 1

8

The sought value is

\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8.

Sample Input 2

6
2 7 1 8 2 8

Sample Output 2

53

Sample Input 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

Sample Output 3

592622

Problem Statement

You are given an integer K. For a set S that is initially empty, process Q queries of the following two types in order:

• 1 x: An integer x is given. If x is in S, remove x from S. Otherwise, add x to S.
• 2 x: An integer x that is in S is given. Consider a graph where the vertices are the numbers in S, and there is an edge between two numbers if and only if the absolute difference between them is at most K. Print the count of vertices in the connected component that contains x.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq K \leq 10^{18}
• For each query, 1 \leq x \leq 10^{18}.
• For each query of the second type, the given x is in S at that point.
• All input values are integers.

Sample Input 1

7 5
1 3
1 10
2 3
1 7
2 3
1 10
2 3

Sample Output 1

1
3
2

The query processing proceeds as follows:

• In the first query, 3 is added to S, resulting in S=\{3\}.
• In the second query, 10 is added to S, resulting in S=\{3,10\}.
• In the third query, consider a graph with vertices 3 and 10 and no edges. The connected component containing 3 has a size of 1, so print 1.
• In the fourth query, 7 is added to S, resulting in S=\{3,7,10\}.
• In the fifth query, consider a graph with vertices 3, 7, and 10, with edges between 3 and 7, and 7 and 10. The connected component containing 3 has a size of 3, so print 3.
• In the sixth query, 10 is removed from S, resulting in S=\{3,7\}.
• In the seventh query, consider a graph with vertices 3 and 7, with an edge between them. The connected component containing 3 has a size of 2, so print 2.

Sample Input 2

11 1000000000000000000
1 1
1 100
1 10000
1 1000000
1 100000000
1 10000000000
1 1000000000000
1 100000000000000
1 10000000000000000
1 1000000000000000000
2 1

Sample Output 2

10

Sample Input 3

8 0
1 1
1 2
2 1
1 1
1 2
1 1
1 2
2 1

Sample Output 3

1
1

Problem Statement

Takahashi can swim in N different styles.
When he swims in the i-th style, he consumes A_i stamina per second and advances B_i meters per second.

Answer Q queries. The i-th query is as follows:

• Determine if it is possible to advance D_i meters while keeping the total stamina consumption at most C_i. If it is possible, find the minimum number of seconds required.

Here, he can freely combine different swimming styles, and the time to switch styles is negligible.
Specifically, he can swim using the following steps:

• Choose a positive integer m, a sequence of positive real numbers t=(t_1,t_2,\dots,t_m) of length m, and a sequence of integers x=(x_1,x_2,\dots,x_m) of length m where each element is between 1 and N, inclusive.
• Then, swim in the x_i-th style for t_i seconds in the order i=1,2,\dots,m.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le A_i, B_i \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le C_i, D_i \le 10^9

Sample Input 1

4
1 2
2 3
3 3
4 4
5
4 7
7 7
49 100
1000 500
4 5

Sample Output 1

3.000000000000000000
1.750000000000000000
-1
125.000000000000000000
1.500000000000000000

In this input, Takahashi can swim in the following four styles:

• Consumes 1 stamina and advances 2 meters per second.
• Consumes 2 stamina and advances 3 meters per second.
• Consumes 3 stamina and advances 3 meters per second.
• Consumes 4 stamina and advances 4 meters per second.

This input contains five queries.

• For the first query, C_1=4, D_1=7.
  • Choose t=(1,2) and x=(2,1). Takahashi swims as follows:
    • In the first 1 second, he consumes 2 stamina and advances 3 meters.
    • In the next 2 seconds, he consumes 2 stamina and advances 4 meters.
  • In total, he consumes 4 stamina and advances 7 meters. The required time is 3 seconds, which is the minimum.
• For the second query, C_2=7, D_2=7.
  • Choose t=(7/4) and x=(4). Takahashi swims as follows:
    • In the first 7/4 seconds, he consumes 7 stamina and advances 7 meters.
  • In total, he consumes 7 stamina and advances 7 meters. The required time is 7/4 seconds, which is the minimum.
• For the third query, C_3=49, D_3=100.
  • No matter how Takahashi swims, it is not possible to advance 100 meters while keeping the total stamina consumption at most 49.
• For the fourth query, C_4=1000, D_4=500.
  • Choose t=(125) and x=(4). Takahashi swims as follows:
    • In the first 125 seconds, he consumes 500 stamina and advances 500 meters.
  • In total, he consumes 500 stamina and advances 500 meters. The required time is 125 seconds, which is the minimum.
• For the fifth query, C_5=4, D_5=5.
  • Choose t=(1/2,1) and x=(4,2). Takahashi swims as follows:
    • In the first 1/2 seconds, he consumes 2 stamina and advances 2 meters.
    • In the next 1 second, he consumes 2 stamina and advances 3 meters.
  • In total, he consumes 4 stamina and advances 5 meters. The required time is 3/2 seconds, which is the minimum.