Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

• If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
• If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
• If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

• 2 \leq N \leq 10 ^ 9
• 1 \leq Q \leq 2\times10 ^ 5
• T _ i=1,2,3\ (1\leq i\leq Q)
• 1 \leq A _ i \leq N\ (1\leq i\leq Q)
• 1 \leq B _ i \leq N\ (1\leq i\leq Q)
• A _ i\neq B _ i\ (1\leq i\leq Q)
• There exists i\ (1\leq i\leq Q) such that T _ i=3.
• All values in the input are integers.

Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

• User 1 follows user 2. No other users are following or followed by any users.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
• User 2 follows user 1.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
• User 2 follows user 3.
• User 3 follows user 2.
• Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
• User 1 unfollows user 2.
• Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

10 30
3 1 6
3 5 4
1 6 1
3 1 7
3 8 4
1 1 6
2 4 3
1 6 5
1 5 6
1 1 8
1 8 1
2 3 10
1 7 6
3 5 6
1 6 7
3 6 7
1 9 5
3 8 6
3 3 8
2 6 9
1 7 1
3 10 8
2 9 2
1 10 9
2 6 10
2 6 8
3 1 6
3 1 8
2 8 5
1 9 10

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Problem Statement

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

Answer Q queries given in the following format.

• You are given integers L, R, and X. Find the number of elements among A_L, \ldots, A_R whose values are equal to X.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq N
• 1 \leq Q \leq 2\times 10^5
• 1\le L \leq R \leq N, 1 \leq X \leq N, for each query.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2
0
0
1

In the first query, two of (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) have values equal to 1.

In the second query, zero of (A_2,A_3,A_4) =(1,4,1) have values equal to 3.

Problem Statement

There is a monster with initial stamina N.
Takahashi repeatedly attacks the monster while the monster's stamina remains 1 or greater.

An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{P}{100} and by 1 with probability 1-\frac{P}{100}.

Find the expected value, modulo 998244353 (see Notes), of the number of attacks before the monster's stamina becomes 0 or less.

Notes

We can prove that the sought expected value is always a finite rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can show that there exists a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print such R.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq P \leq 100
• All values in the input are integers.

Sample Input 1

3 10

Sample Output 1

229596204

An attack by Takahashi reduces the monster's stamina by 2 with probability \frac{10}{100}=\frac{1}{10} and by 1 with probability \frac{100-10}{100}=\frac{9}{10}.

• The monster's initial stamina is 3.
• After the first attack, the monster's stamina is 2 with probability \frac{9}{10} and 1 with probability \frac{1}{10}.
• After the second attack, the monster's stamina is 1 with probability \frac{81}{100}, 0 with probability \frac{18}{100}, and -1 with probability \frac{1}{100}. With probability \frac{18}{100}+\frac{1}{100}=\frac{19}{100}, the stamina becomes 0 or less, and Takahashi stops attacking after two attacks.
• If the stamina remains 1 after two attacks, the monster's stamina always becomes 0 or less by the third attack, so he stops attacking after three attacks.

Therefore, the expected value is 2\times \frac{19}{100}+3\times\left(1-\frac{19}{100}\right)=\frac{281}{100}. Since 229596204 \times 100 \equiv 281\pmod{998244353}, print 229596204.

Sample Input 2

5 100

Sample Output 2

3

Takahashi's attack always reduces the monster's stamina by 2. After the second attack, the stamina remains 5-2\times 2=1, so the third one is required.

Sample Input 3

280 59

Sample Output 3

567484387

Problem Statement

You are given a positive integer X with N digits in decimal representation. None of the digits of X is 0.
For a subset S of \lbrace 1,2, \ldots, N-1 \rbrace , let f(S) be defined as follows.

See the decimal representation of X as a string of length N, and decompose it into |S| + 1 strings by splitting it between the i-th and (i + 1)-th characters if and only if i \in S.
Then, see these |S| + 1 strings as integers in decimal representation, and let f(S) be the product of these |S| + 1 integers.

There are 2^{N-1} subsets of \lbrace 1,2, \ldots, N-1 \rbrace , including the empty set, which can be S. Find the sum of f(S) over all these S, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• X has N digits in decimal representation, none of which is 0.
• All values in the input are integers.

Sample Input 1

3
234

Sample Output 1

418

For S = \emptyset, we have f(S) = 234.
For S = \lbrace 1 \rbrace, we have f(S) = 2 \times 34 = 68.
For S = \lbrace 2 \rbrace, we have f(S) = 23 \times 4 = 92.
For S = \lbrace 1, 2 \rbrace, we have f(S) = 2 \times 3 \times 4 = 24.
Thus, you should print 234 + 68 + 92 + 24 = 418.

Sample Input 2

4
5915

Sample Output 2

17800

Sample Input 3

9
998244353

Sample Output 3

258280134