Problem Statement

You are given a real number X.Y, where Y is a single digit.

Print the following: (quotes for clarity)

• X-, if 0 \leq Y \leq 2;
• X, if 3 \leq Y \leq 6;
• X+, if 7 \leq Y \leq 9.

Constraints

• 1 \leq X \leq 15
• 0 \leq Y \leq 9
• X and Y are integers.

Sample Input 1

15.8

Sample Output 1

15+

Here, printing 15 + will not be accepted: do not print a space between X and +, or between X and -.

Sample Input 2

1.0

Sample Output 2

1-

You will not get inputs such as 1.00 and 1.

Sample Input 3

12.5

Sample Output 3

12

Problem Statement

There are N people. The family name and given name of the i-th person (1 \leq i \leq N) are S_i and T_i, respectively.

Determine whether there is a pair of people with the same family and given names. In other words, determine whether there is a pair of integers (i,j) such that 1 \leq i \lt j \leq N, S_i=S_j, and T_i=T_j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• Each of S_i and T_i is a string of length between 1 and 10 (inclusive) consisting of English lowercase letters.

Sample Input 1

3
tanaka taro
sato hanako
tanaka taro

Sample Output 1

Yes

The first and third persons have the same family and given names.

Sample Input 2

3
saito ichiro
saito jiro
saito saburo

Sample Output 2

No

No two persons have the same family and given names.

Sample Input 3

4
sypdgidop bkseq
bajsqz hh
ozjekw mcybmtt
qfeysvw dbo

Sample Output 3

No

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.

These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.

Your objective is to empty all M cylinders by repeating the following operation.

• Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq k_i\ (1 \leq i \leq M)
• 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
• \sum_{i=1}^{M} k_i = 2N
• For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
• All values in input are integers.

Sample Input 1

2 2
2
1 2
2
1 2

Sample Output 1

Yes

The objective can be achieved as follows.

1. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
2. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.

Sample Input 2

2 2
2
1 2
2
2 1

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.

Problem Statement

Takahashi has come to an amusement park.
The park has N attractions. The fun of the i-th attraction is initially a_i.

When Takahashi rides the i-th attraction, the following sequence of events happens.

• Takahashi's satisfaction increases by the current fun of the i-th attraction.
• Then, the fun of the i-th attraction decreases by 1.

Takahashi's satisfaction is initially 0. He can ride the attractions at most K times in total in any order.
What is the maximum possible value of satisfaction Takahashi can end up with?

Other than riding the attractions, nothing affects Takahashi's satisfaction.

Constraints

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

Sample Input 1

3 5
100 50 102

Sample Output 1

502

Takahashi should ride the first attraction twice and the third attraction three times.
He will end up with the satisfaction of (100+99)+(102+101+100)=502.
There is no way to get the satisfaction of 503 or more, so the answer is 502.

Sample Input 2

2 2021
2 3

Sample Output 2

9

Takahashi may choose to ride the attractions fewer than K times in total.

Problem Statement

Given are sequences of N integers each: A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N). Find the number of non-empty subsets S of \{1,2,\ldots,N\} that satisfy the following condition:

• \max_{i \in S} A_i \geq \sum_{i \in S} B_i.

Since the count can be enormous, print it modulo 998244353.

Constraints

• 1 \leq N \leq 5000
• 1 \leq A_i,B_i \leq 5000
• All values in input are integers.

Sample Input 1

2
3 1
1 2

Sample Output 1

2

\{1,2,\ldots,N\} has three subsets: \{1\}, \{2\}, and \{1,2\}.

• For S=\{1\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=1.
• For S=\{2\}, we have \max_{i \in S} A_i=1 and \sum_{i \in S} B_i=2.
• For S=\{1,2\}, we have \max_{i \in S} A_i=3 and \sum_{i \in S} B_i=3.

Thus, the condition \max_{i \in S} A_i \geq \sum_{i \in S} B_i is satisfied by two subsets: \{1\} and \{1,2\}.

Sample Input 2

2
1 1
2 2

Sample Output 2

0

There may be no subsets that satisfy the condition.

Sample Input 3

20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

Sample Output 3

476

Problem Statement

Consider a sequence of length N consisting of 0s and 1s, A=(A_1,A_2,\dots,A_N), that satisfies the following condition.

For every i=1,2,\dots,M, there are at least X_i occurrences of 1 among A_{L_i}, A_{L_i+1}, \dots, A_{R_i}.

Print one such sequence with the fewest number of occurrences of 1s.

There always exists a sequence that satisfies the condition under the Constraints.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min(2 \times 10^5, \frac{N(N+1)}{2} )
• 1 \leq L_i \leq R_i \leq N
• 1 \leq X_i \leq R_i-L_i+1
• (L_i,R_i) \neq (L_j,R_j) if i \neq j.
• All values in input are integers.

Sample Input 1

6 3
1 4 3
2 2 1
4 6 2

Sample Output 1

0 1 1 1 0 1 

Another acceptable output is 1 1 0 1 1 0.
On the other hand, 0 1 1 1 1 1, which has more than the fewest number of 1s, is unacceptable.

Sample Input 2

8 2
2 6 1
3 5 3

Sample Output 2

0 0 1 1 1 0 0 0 

Problem Statement

There are K robots on a number line. The i-th robot (1 \leq i \leq K) is initially at the coordinate x_i.

The following procedure is going to take place exactly N times.

• Each robot chooses to move or not with probability \frac{1}{2} each. The robots that move will simultaneously go the distance of 1 in the positive direction, and the other robots will remain still.

Here, all probabilistic decisions are independent.

Find the probability that no two robots meet, that is, there are never two or more robots at the same coordinate at the same time throughout the procedures, modulo 998244353 (see Notes).

Notes

It can be proved that the probability in question is always a rational number. Additionally, under the Constraints in this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there uniquely exists an integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \leq K \leq 10
• 1 \leq N \leq 1000
• 0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000
• All values in input are integers.

Sample Input 1

2 2
1 2

Sample Output 1

374341633

The probability in question is \frac{5}{8}.

We have 374341633 \times 8 \equiv 5\pmod{998244353}, so you should print 374341633.

Sample Input 2

2 2
10 100

Sample Output 2

1

The probability in question may be 1.

Sample Input 3

10 832
73 160 221 340 447 574 720 742 782 970

Sample Output 3

553220346