Problem Statement

In AtCoder City, there are three stations numbered 1, 2, and 3.

Each of these stations is operated by one of the two railway companies, A and B. A string S of length 3 represents which company operates each station. If S_i is A, Company A operates Station i; if S_i is B, Company B operates Station i.

To improve the transportation condition, for each pair of a station operated by Company A and one operated by Company B, there will be a bus service connecting them.

Determine if there is a pair of stations that will be connected by a bus service.

Constraints

• Each character of S is A or B.
• |S| = 3

Sample Input 1

ABA

Sample Output 1

Yes

Company A operates Station 1 and 3, while Company B operates Station 2.

There will be a bus service between Station 1 and 2, and between Station 2 and 3, so print Yes.

Sample Input 2

BBA

Sample Output 2

Yes

Company B operates Station 1 and 2, while Company A operates Station 3.

There will be a bus service between Station 1 and 3, and between Station 2 and 3, so print Yes.

Sample Input 3

BBB

Sample Output 3

No

Company B operates all the stations. Thus, there will be no bus service, so print No.

Problem Statement

Takahashi has many red balls and blue balls. Now, he will place them in a row.

Initially, there is no ball placed.

Takahashi, who is very patient, will do the following operation 10^{100} times:

• Place A blue balls at the end of the row of balls already placed. Then, place B red balls at the end of the row.

How many blue balls will be there among the first N balls in the row of balls made this way?

Constraints

• 1 \leq N \leq 10^{18}
• A, B \geq 0
• 0 < A + B \leq 10^{18}
• All values in input are integers.

Sample Input 1

8 3 4

Sample Output 1

4

Let b denote a blue ball, and r denote a red ball. The first eight balls in the row will be bbbrrrrb, among which there are four blue balls.

Sample Input 2

8 0 4

Sample Output 2

0

He placed only red balls from the beginning.

Sample Input 3

6 2 4

Sample Output 3

2

Among bbrrrr, there are two blue balls.

Problem Statement

Find the price of a product before tax such that, when the consumption tax rate is 8 percent and 10 percent, the amount of consumption tax levied on it is A yen and B yen, respectively. (Yen is the currency of Japan.)

Here, the price before tax must be a positive integer, and the amount of consumption tax is rounded down to the nearest integer.

If multiple prices satisfy the condition, print the lowest such price; if no price satisfies the condition, print -1.

Constraints

• 1 \leq A \leq B \leq 100
• A and B are integers.

Sample Input 1

2 2

Sample Output 1

25

If the price of a product before tax is 25 yen, the amount of consumption tax levied on it is:

• When the consumption tax rate is 8 percent: \lfloor 25 \times 0.08 \rfloor = \lfloor 2 \rfloor = 2 yen.
• When the consumption tax rate is 10 percent: \lfloor 25 \times 0.1 \rfloor = \lfloor 2.5 \rfloor = 2 yen.

Thus, the price of 25 yen satisfies the condition. There are other possible prices, such as 26 yen, but print the minimum such price, 25.

Sample Input 2

8 10

Sample Output 2

100

If the price of a product before tax is 100 yen, the amount of consumption tax levied on it is:

• When the consumption tax rate is 8 percent: \lfloor 100 \times 0.08 \rfloor = 8 yen.
• When the consumption tax rate is 10 percent: \lfloor 100 \times 0.1 \rfloor = 10 yen.

Sample Input 3

19 99

Sample Output 3

-1

There is no price before tax satisfying this condition, so print -1.

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

Starting with this string, he will produce a new one in the procedure given as follows.

The procedure consists of Q operations. In Operation i (1 \leq i \leq Q), an integer T_i is provided, which means the following:

• If T_i = 1: reverse the string S.

• If T_i = 2: An integer F_i and a lowercase English letter C_i are additionally provided.

  • If F_i = 1 : Add C_i to the beginning of the string S.
  • If F_i = 2 : Add C_i to the end of the string S.

Help Takahashi by finding the final string that results from the procedure.

Constraints

• 1 \leq |S| \leq 10^5
• S consists of lowercase English letters.
• 1 \leq Q \leq 2 \times 10^5
• T_i = 1 or 2.
• F_i = 1 or 2, if provided.
• C_i is a lowercase English letter, if provided.

Sample Input 1

a
4
2 1 p
1
2 2 c
1

Sample Output 1

cpa

There will be Q = 4 operations. Initially, S is a.

• Operation 1: Add p at the beginning of S. S becomes pa.

• Operation 2: Reverse S. S becomes ap.

• Operation 3: Add c at the end of S. S becomes apc.

• Operation 4: Reverse S. S becomes cpa.

Thus, the resulting string is cpa.

Sample Input 2

a
6
2 2 a
2 1 b
1
2 2 c
1
1

Sample Output 2

aabc

There will be Q = 6 operations. Initially, S is a.

• Operation 1: S becomes aa.

• Operation 2: S becomes baa.

• Operation 3: S becomes aab.

• Operation 4: S becomes aabc.

• Operation 5: S becomes cbaa.

• Operation 6: S becomes aabc.

Thus, the resulting string is aabc.

Sample Input 3

y
1
2 1 x

Sample Output 3

xy

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S consists of digits.
• |S| = N
• 2 \leq P \leq 10000
• P is a prime number.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

• 3: divisible by 3.

• 35: not divisible by 3.

• 354: divisible by 3.

• 3543: divisible by 3.

• 5: not divisible by 3.

• 54: divisible by 3.

• 543: divisible by 3.

• 4: not divisible by 3.

• 43: not divisible by 3.

• 3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68

Problem Statement

There are N robots numbered 1 to N placed on a number line. Robot i is placed at coordinate X_i. When activated, it will travel the distance of D_i in the positive direction, and then it will be removed from the number line. All the robots move at the same speed, and their sizes are ignorable.

Takahashi, who is a mischievous boy, can do the following operation any number of times (possibly zero) as long as there is a robot remaining on the number line.

• Choose a robot and activate it. This operation cannot be done when there is a robot moving.

While Robot i is moving, if it touches another robot j that is remaining in the range [X_i, X_i + D_i) on the number line, Robot j also gets activated and starts moving. This process is repeated recursively.

How many possible sets of robots remaining on the number line are there after Takahashi does the operation some number of times? Compute this count modulo 998244353, since it can be enormous.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i \leq 10^9
• 1 \leq D_i \leq 10^9
• X_i \neq X_j (i \neq j)
• All values in input are integers.

Sample Input 1

2
1 5
3 3

Sample Output 1

3

There are three possible sets of robots remaining on the number line: \{1, 2\}, \{1\}, and \{\}.

These can be achieved as follows:

• If Takahashi activates nothing, the robots \{1, 2\} will remain.

• If Takahashi activates Robot 1, it will activate Robot 2 while moving, after which there will be no robots on the number line. This state can also be reached by activating Robot 2 and then Robot 1.

• If Takahashi activates Robot 2 and finishes doing the operation, the robot \{1\} will remain.

Sample Input 2

3
6 5
-1 10
3 3

Sample Output 2

5

There are five possible sets of robots remaining on the number line: \{1, 2, 3\}, \{1, 2\}, \{2\}, \{2, 3\}, and \{\}.

Sample Input 3

4
7 10
-10 3
4 3
-4 3

Sample Output 3

16

None of the robots influences others.

Sample Input 4

20
-8 1
26 4
0 5
9 1
19 4
22 20
28 27
11 8
-3 20
-25 17
10 4
-18 27
24 28
-11 19
2 27
-2 18
-1 12
-24 29
31 29
29 7

Sample Output 4

110

Remember to print the count modulo 998244353.