Problem Statement

Given integers W and B, solve the following problem.

Takahashi's weight is W {\rm [kg]}. (Note that the unit is {\rm kg}.)
An object attached with n balloons will fly into the sky if and only if the mass of the object is strictly less than nB {\rm [g]}.
What is the minimum number of balloons needed to make Takahashi fly into the sky?

Constraints

• 1 \le W \le 100
• 1 \le B \le 100
• All input values are integers.

Sample Input 1

80 5

Sample Output 1

16001

Takahashi's weight is 80 {\rm kg} = 80000 {\rm g}.
If he is attached with 16001 balloons, his mass is less than 16001 \times 5=80005 {\rm g}, so he will fly into the sky.
Note that 16000 balloons are not sufficient.

Sample Input 2

70 6

Sample Output 2

11667

Sample Input 3

100 100

Sample Output 3

1001

Problem Statement

There are N birds of M types flying in the sky.
The bird types are numbered 1,2,\dots,M.
The N birds are numbered 1,2,\dots,N, and bird i is of type A_i and has size B_i.

For every k=1,2,\dots,M, find the average size of the flying birds of type k.
It is guaranteed that for every k=1,2,\dots,M, there is at least one bird of type k flying.

Constraints

• 1 \le M \le N \le 100
• 1 \le A_i \le M
• 1 \le B_i \le 100
• There exists at least one bird of type k ( 1 \le k \le M ).
• All input values are integers.

Sample Input 1

10 5
4 92
1 16
3 77
4 99
2 89
3 8
1 40
5 56
1 40
4 77

Sample Output 1

32.00000000000000000000
89.00000000000000000000
42.50000000000000000000
89.33333333333333333333
56.00000000000000000000

• The average size of birds of type 1 is (16+40+40)/3 = 32.
• The average size of birds of type 2 is 89.
• The average size of birds of type 3 is (77+8)/2 = 42.5.
• The average size of birds of type 4 is (92+99+77)/3 \approx 89.3333.
• The average size of birds of type 5 is 56.

Problem Statement

Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude H at time 0 (the unit is seconds), and will fly for 10^9 seconds from now.

Takahashi can change his flying altitude by up to 1 per second. However, he cannot make his altitude 0 or less.

• In other words, if F(t) denotes Takahashi's altitude at time t, then F(t) satisfies all of the following conditions:
  • F(0) = H
  • -1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1 for 0 \leq t \lt u \leq 10^9.
  • F(t) \gt 0 for 0 \leq t \leq 10^9.

There are N goals regarding altitude. The i-th goal is to make the altitude at time t_i at least l_i and at most u_i.
Is it possible for Takahashi to fly in a way that achieves all goals?

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

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq H \leq 10^9
• 1 \leq t_1 \lt t_2 \lt \dots \lt t_N \leq 10^9
• 1 \leq l_i \leq u_i \leq 10^9
• The sum of N over all test cases is at most 10^5.
• All input values are integers.

Sample Input 1

3
2 5
3 1 4
8 9 11
2 6
1 1 4
3 5 8
10 36
27 37 38
30 34 54
38 20 77
45 1 36
49 38 51
52 31 58
65 43 60
71 14 42
73 36 38
85 14 29

Sample Output 1

Yes
No
Yes

For the first test case, Takahashi can achieve all goals by flying as follows:

• At time 0, he is at altitude 5.
• From time 0 to time 2, he descends at a rate of 0.5 per second.
• At time 2, he is at altitude 5 - 0.5 \times 2 = 4.
• From time 2 to time 3, he stays at the same altitude.
• At time 3, he is at altitude 4. He satisfies the first goal.
• From time 3 to time 8, he ascends at a rate of 1 per second.
• At time 8, he is at altitude 4 + 1 \times 5 = 9. He satisfies the second goal.

For the second test case, he cannot achieve all goals no matter how he flies.

Problem Statement

The sky is represented by a 2000 \times 2000 grid.
When looking up at the sky, the cell at the r-th row from the top and c-th column from the left is called (r,c).

Currently, there are clouds 1,2,\dots,N floating in this sky.
The cell (r,c) is covered by cloud i if and only if it satisfies U_i \le r \le D_i and L_i \le c \le R_i.

For k=1,2,\dots,N, answer the following question:

• Remove only cloud k from the N clouds. At this point, there are N-1 clouds floating in the sky. How many cells are not covered by any cloud?

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le U_i \le D_i \le 2000
• 1 \le L_i \le R_i \le 2000
• All input values are integers.

Sample Input 1

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

Sample Output 1

3999983
3999976
3999982
3999978
3999977

The figure shows the top-left 5 \times 6 region of the sky.

• When cloud 1 is removed, the number of cells covered by some cloud is 17, so the number of cells not covered by any cloud is 3999983.
• When cloud 2 is removed, the number of cells covered by some cloud is 24, so the number of cells not covered by any cloud is 3999976.
• When cloud 3 is removed, the number of cells covered by some cloud is 18, so the number of cells not covered by any cloud is 3999982.
• When cloud 4 is removed, the number of cells covered by some cloud is 22, so the number of cells not covered by any cloud is 3999978.
• When cloud 5 is removed, the number of cells covered by some cloud is 23, so the number of cells not covered by any cloud is 3999977.

Problem Statement

There are N rabbits numbered 1 to N on a number line. Rabbit i is at coordinate X_i. Multiple rabbits may be at the same coordinate.
Each rabbit has a parameter called jumping power, and rabbit i has jumping power R_i.
Now, all rabbits will jump exactly once. When a rabbit at coordinate x with jumping power r jumps, it moves to coordinate x+r or coordinate x-r.
If you can freely choose which coordinate each rabbit jumps to, find the maximum possible number of distinct coordinates where rabbits are present after all rabbits have jumped.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i \leq 10^9
• 1 \leq R_i \leq 10^9
• All input values are integers.

Sample Input 1

3
4 1
2 3
4 5

Sample Output 1

3

If each rabbit moves as shown below, it is possible to achieve 3 as the number of distinct coordinates where rabbits are present after jumping, and this is the maximum possible.

• Rabbit 1 moves to 4 - 1 = 3.
• Rabbit 2 moves to 2 + 3 = 5.
• Rabbit 3 moves to 4 - 5 = -1.

Sample Input 2

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

Sample Output 2

4

If each rabbit moves as shown below, it is possible to achieve 4 as the number of distinct coordinates where rabbits are present after jumping, and this is the maximum possible.

• Rabbit 1 moves to 2 - 1 = 1.
• Rabbit 2 moves to 3 + 2 = 5.
• Rabbit 3 moves to 6 + 1 = 7.
• Rabbit 4 moves to 5 + 2 = 7.
• Rabbit 5 moves to 4 - 3 = 1.
• Rabbit 6 moves to 4 - 1 = 3.

Sample Input 3

10
1000000000 1000000000
1000000000 1
-1000000000 1000000000
-1000000000 1
0 1
2 1
1 2
4 1
3 2
4 3

Sample Output 3

9

Problem Statement

You are given N strings S_i consisting of lowercase English letters.

For all possible permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), write down the string generated as follows:

• Concatenate S_{P_1},S_{P_2},\dots,S_{P_N} in this order.

Let A_1,A_2,\dots,A_{N!} be the sequence of the N! written strings sorted in lexicographical order.
Output A_2.

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

Constraints

• 1 \le T \le 1.5 \times 10^5
• 2 \le N \le 3 \times 10^5
• T,N are integers.
• S_i is a string consisting of lowercase English letters with length between 1 and 10^6-1, inclusive.
• For a single input, the sum of N does not exceed 3 \times 10^5.
• For a single input, the sum of |S_i| does not exceed 10^6.

Sample Input 1

3
3
abc
ac
ahc
4
aaa
a
aaaa
a
15
ks
sy
k
ysk
yks
ky
ksy
sk
syk
s
kys
sky
ys
yk
y

Sample Output 1

abcahcac
aaaaaaaaa
kksksykykysskskyssyksyyksykyskyys

This input contains three test cases.

For the first test case, S=( abc, ac, ahc ).
We have A=( abcacahc, abcahcac, acabcahc, acahcabc, ahcabcac, ahcacabc ), so output A_2= abcahcac.

Problem Statement

For a string A consisting of 1, 2, \dots, 9 and B, define f(A) as the string obtained by the following procedure:

• Initially, there is an empty string C.
• Perform the following operations in the order i = 1, 2, \dots, |A|:
  • If A_i is one of 1, 2, \dots, 9, append A_i to the end of C.
  • If A_i = B, delete the last character of C. However, if C is an empty string, do nothing.
• Let f(A) be C after completing all the above operations.

You are given a string S of length N consisting of 1, 2, \dots, 9, and B.
Process Q queries described below. Each query is of one of the following two types:

• 1\ \ x\ \ c : Update S_x to c. (Here, c is 1, 2, \dots, 9, or B.)
• 2\ \ l\ \ r : Let T be the string formed by extracting the l-th through r-th characters of S. Then, let U=f(T). If U is an empty string, output -1; otherwise, output the remainder when the value of U regarded as a decimal integer is divided by 998244353.

Constraints

• 1 \leq N \leq 8 \times 10^6
• 1 \leq Q \leq 2 \times 10^5
• S is a string of length N consisting of 1, 2, \dots, 9, and B.
• 1 \leq x \leq N
• c is 1, 2, \dots, 9, or B.
• 1 \leq l \leq r \leq N
• N, Q, x, l, r are integers.

Sample Input 1

10 12
1234567891
2 5 7
2 2 8
2 1 10
1 3 B
1 4 B
2 2 4
2 2 8
2 1 10
1 7 B
2 3 9
1 3 4
2 1 10

Sample Output 1

567
2345678
236323538
-1
5678
567891
589
125891

For the first query, T=U= 567. Thus, output 567.
For the third query, T=U= 1234567891. Thus, output 1234567891 \bmod 998244353 = 236323538.
For the sixth query, T= 2BB and U is an empty string. Thus, output -1.