Problem Statement

You are given integers A, B, C. If A \neq B and B = C, output Yes; otherwise, output No.

Constraints

• 1 \leq A, B, C \leq 9
• All input values are integers.

Sample Input 1

4 5 5

Sample Output 1

Yes

Since 4 \neq 5 and 5 = 5, output Yes.

Sample Input 2

1 3 7

Sample Output 2

No

Although 1 \neq 3, we don't have 3 = 7, so output No.

Sample Input 3

6 6 6

Sample Output 3

No

Problem Statement

AtCoder Regular Contest (ARC) currently has two divisions: Div. 1 and Div. 2. In ARC Div. 1, participants whose rating is between 1600 and 2999, inclusive, are rated. In ARC Div. 2, participants whose rating is between 1200 and 2399, inclusive, are rated.

You are given positive integers R and X.

Determine whether a person with rating R is rated in ARC Div. X.

Constraints

• 1 \le R \le 4229
• 1 \le X \le 2
• All input values are integers.

Sample Input 1

2000 1

Sample Output 1

Yes

Because 2000 lies between 1600 and 2999, a person with rating 2000 is rated in ARC Div. 1.

Sample Input 2

1000 1

Sample Output 2

No

Because 1000 is less than 1600, a person with rating 1000 is not rated in ARC Div. 1.

Sample Input 3

1500 2

Sample Output 3

Yes

Because 1500 lies between 1200 and 2399, a person with rating 1500 is rated in ARC Div. 2.

Sample Input 4

2800 2

Sample Output 4

No

Because 2800 exceeds 2399, a person with rating 2800 is not rated in ARC Div. 2.

Problem Statement

You are given an integer N.
Print an approximation of N according to the following instructions.

• If N is less than or equal to 10^3-1, print N as it is.
• If N is between 10^3 and 10^4-1, inclusive, truncate the ones digit of N and print the result.
• If N is between 10^4 and 10^5-1, inclusive, truncate the tens digit and all digits below it of N and print the result.
• If N is between 10^5 and 10^6-1, inclusive, truncate the hundreds digit and all digits below it of N and print the result.
• If N is between 10^6 and 10^7-1, inclusive, truncate the thousands digit and all digits below it of N and print the result.
• If N is between 10^7 and 10^8-1, inclusive, truncate the ten-thousands digit and all digits below it of N and print the result.
• If N is between 10^8 and 10^9-1, inclusive, truncate the hundred-thousands digit and all digits below it of N and print the result.

Constraints

• N is an integer between 0 and 10^9-1, inclusive.

Sample Input 1

20230603

Sample Output 1

20200000

20230603 is between 10^7 and 10^8-1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print 20200000.

Sample Input 2

0

Sample Output 2

0

Sample Input 3

304

Sample Output 3

304

Sample Input 4

500600

Sample Output 4

500000

Problem Statement

You are given a string S of length N consisting of o and x.
N chairs are arranged in a row from left to right. If the i-th character of S is o, a person is sitting in the i-th chair from the left; if it is x, no person is sitting there.
Find the number of chairs that satisfy all of the following conditions.

• No person is sitting in it.
• There is no chair to its left, or no person is sitting in the chair to its left.
• There is no chair to its right, or no person is sitting in the chair to its right.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of o and x.

Sample Input 1

8
xxoxxxox

Sample Output 1

2

Only the first and fifth chairs from the left satisfy the conditions.

Sample Input 2

5
ooooo

Sample Output 2

0

Sample Input 3

1
x

Sample Output 3

1

Problem Statement

In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.

Turret i guards castle walls numbered from L_i through R_i.

When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.

What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

10 4
1 6
4 5
5 10
7 10

Sample Output 1

1

If turret 1 is destroyed, no turret guards castle wall 3. Also, if no turrets are destroyed, all castle walls are guarded by some turret. Therefore, output 1.

Sample Input 2

5 2
1 2
3 4

Sample Output 2

0

Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.

Sample Input 3

5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

Sample Output 3

3

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

Find the sum of integers between 1 and N (inclusive) that are not multiples of A or B.

Constraints

• 1 \leq N, A,B \leq 10^9
• All values in input are integers.

Sample Input 1

10 3 5

Sample Output 1

22

The integers between 1 and 10 (inclusive) that are not multiples of 3 or 5 are 1,2,4,7, and 8, whose sum is 1+2+4+7+8 =22.

Sample Input 2

1000000000 314 159

Sample Output 2

495273003954006262

Problem Statement

You are given a sequence X of length N where each element is between 1 and N, inclusive, and a sequence A of length N.
Print the result of performing the following operation K times on A.

• Replace A with B such that B_i = A_{X_i}.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le K \le 10^{18}
• 1 \le X_i \le N
• 1 \le A_i \le 2 \times 10^5

Sample Input 1

7 3
5 2 6 3 1 4 6
1 2 3 5 7 9 11

Sample Output 1

7 2 3 5 1 9 3

In this input, X=(5,2,6,3,1,4,6) and the initial sequence is A=(1,2,3,5,7,9,11).

• After one operation, the sequence is (7,2,9,3,1,5,9).
• After two operations, the sequence is (1,2,5,9,7,3,5).
• After three operations, the sequence is (7,2,3,5,1,9,3).

Sample Input 2

4 0
3 4 1 2
4 3 2 1

Sample Output 2

4 3 2 1

There may be cases where no operations are performed.

Sample Input 3

9 1000000000000000000
3 7 8 5 9 3 7 4 2
9 9 8 2 4 4 3 5 3

Sample Output 3

3 3 3 3 3 3 3 3 3

Problem Statement

A tournament is being held with 2N players. From now on, each player will play exactly one match. In the remaining N matches, the i-th (1\le i\le N) match is played between the (2i-1)-th and 2i-th players.

In each match, one of the two competing players wins and the other loses. Which player wins is determined independently for each match, and each player wins with probability \dfrac12.

Before the last N matches begin, the i-th (1\le i\le2N) player has won A _ i times. After all matches are over, the champion is chosen from among the players with the most wins, uniformly at random and independently of the previous match results.

For each of the first, second, \ldots, 2N-th players, find the probability, modulo 998244353, of that player becoming the champion.

Constraints

• 1\le N\le2\times10 ^ 5
• 0\le A _ i\lt2N\ (1\le i\le 2N)
• All input values are integers.

Sample Input 1

4
1 2
3 4
2 3
1 4

Sample Output 1

0 0 259959467 883862188 0 967049217 0 883862188

For example, the third player becomes the champion in the following cases:

• If the third player wins in the second match, the fifth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability \dfrac13.
• If the third player wins in the second match, the sixth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability \dfrac14.

Thus, the probability of the third player becoming the champion is \dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96}. We have 259959467\times96\equiv7\pmod{998244353}, so the probability of the third player becoming the champion in modulo-998244353 expression is 259959467.

The probability of each player becoming the champion is 0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96}. Thus, output 0 0 259959467 883862188 0 967049217 0 883862188.

Sample Input 2

6
0 0
0 0
0 0
0 0
0 0
0 0

Sample Output 2

582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206 582309206

It is possible that no one has won yet.

By symmetry, each player becomes the champion with probability \dfrac1{12}.

Sample Input 3

10
18 17
16 18
18 16
16 16
17 17
16 16
17 16
17 18
16 16
17 18

Sample Output 3

357877533 151989635 0 357877533 357877533 0 0 0 575116994 575116994 0 0 597386855 0 151989635 357877533 0 0 151989635 357877533