Problem Statement

You are given a string S of length 6. It is guaranteed that the first three characters of S are ABC and the last three characters are digits.

Determine if S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest.

Here, a string T is "the abbreviation of a contest held and concluded on AtCoder before the start of this contest" if and only if it equals one of the following 348 strings:

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349.

Note that ABC316 is not included.

Constraints

• S is a string of length 6 where the first three characters are ABC and the last three characters are digits.

Sample Input 1

ABC349

Sample Output 1

Yes

ABC349 is the abbreviation of a contest held and concluded on AtCoder last week.

Sample Input 2

ABC350

Sample Output 2

No

ABC350 is this contest, which has not concluded yet.

Sample Input 3

ABC316

Sample Output 3

No

ABC316 was not held on AtCoder.

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

• If there is a tooth in hole T_i, remove the tooth from hole T_i.
• If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

• All input values are integers.
• 1 \le N, Q \le 1000
• 1 \le T_i \le N

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

28

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

• In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
• In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
• In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
• In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
• In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
• In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

5

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

• Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

• 2 \leq N \leq 2\times 10^5
• (A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

• Initially, A=(3,4,1,2,5).
• The first operation swaps the first and third elements, making A=(1,4,3,2,5).
• The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

4
2 3
3 4
1 2
2 3

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

Problem Statement

There is an SNS used by N users, labeled with numbers from 1 to N.

In this SNS, two users can become friends with each other.
Friendship is bidirectional; if user X is a friend of user Y, user Y is always a friend of user X.

Currently, there are M pairs of friendships on the SNS, with the i-th pair consisting of users A_i and B_i.

Determine the maximum number of times the following operation can be performed:

• Operation: Choose three users X, Y, and Z such that X and Y are friends, Y and Z are friends, but X and Z are not. Make X and Z friends.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N
• The pairs (A_i, B_i) are distinct.
• All input values are integers.

Sample Input 1

4 3
1 2
2 3
1 4

Sample Output 1

3

Three new friendships with a friend's friend can occur as follows:

• User 1 becomes friends with user 3, who is a friend of their friend (user 2)
• User 3 becomes friends with user 4, who is a friend of their friend (user 1)
• User 2 becomes friends with user 4, who is a friend of their friend (user 1)

There will not be four or more new friendships.

Sample Input 2

3 0

Sample Output 2

0

If there are no initial friendships, no new friendships can occur.

Sample Input 3

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

Sample Output 3

12

Problem Statement

You are given an integer N. You can perform the following two types of operations:

• Pay X yen to replace N with \displaystyle\left\lfloor\frac{N}{A}\right\rfloor.
• Pay Y yen to roll a die (dice) that shows an integer between 1 and 6, inclusive, with equal probability. Let b be the outcome of the die, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

Here, \lfloor s \rfloor denotes the greatest integer less than or equal to s. For example, \lfloor 3 \rfloor=3 and \lfloor 2.5 \rfloor=2.

Determine the minimum expected cost paid before N becomes 0 when optimally choosing operations.
The outcome of the die in each operation is independent of other rolls, and the choice of operation can be made after observing the results of the previous operations.

Constraints

• 1 \leq N \leq 10^{18}
• 2 \leq A \leq 6
• 1 \leq X, Y \leq 10^9
• All input values are integers.

Sample Input 1

3 2 10 20

Sample Output 1

20.000000000000000

The available operations are as follows:

• Pay 10 yen. Replace N with \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
• Pay 20 yen. Roll a die. Let b be the outcome, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

The optimal strategy is to perform the first operation twice.

Sample Input 2

3 2 20 20

Sample Output 2

32.000000000000000

The available operations are as follows:

• Pay 20 yen. Replace N with \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
• Pay 20 yen. Roll a die. Let b be the outcome, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

The optimal strategy is as follows:

• First, perform the second operation to roll the die.
  • If the outcome is 4 or greater, then N becomes 0.
  • If the outcome is 2 or 3, then N becomes 1. Now, perform the first operation to make N = 0.
  • If the outcome is 1, restart from the beginning.

Sample Input 3

314159265358979323 4 223606797 173205080

Sample Output 3

6418410657.7408381

Problem Statement

You are given a string S = S_1 S_2 S_3 \dots S_{|S|} consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string S are properly matched.

Repeat the following operation until no more operations can be performed:

• First, select one pair of integers (l, r) that satisfies all of the following conditions:
  • l < r
  • S_l = (
  • S_r = )
  • Each of the characters S_{l+1}, S_{l+2}, \dots, S_{r-1} is an uppercase or lowercase English letter.
• Let T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
  • Here, \overline{x} denotes the string obtained by toggling the case of each character in x (uppercase to lowercase and vice versa).
• Then, delete the l-th through r-th characters of S and insert T at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

Constraints

• 1 \le |S| \le 5 \times 10^5
• S consists of uppercase and lowercase English letters, (, and ).
• The parentheses in S are properly matched.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for S = ((A)y)x.

• Choose l=2 and r=4. The substring (A) is removed and replaced with a.
  • After this operation, S = (ay)x.
• Choose l=1 and r=4. The substring (ay) is removed and replaced with YA.
  • After this operation, S = YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

((XYZ)n(X(y)Z))

Sample Output 2

XYZNXYZ

Let us perform the operations for S = ((XYZ)n(X(y)Z)).

• Choose l=10 and r=12. The substring (y) is removed and replaced with Y.
  • After this operation, S = ((XYZ)n(XYZ)).
• Choose l=2 and r=6. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxn(XYZ)).
• Choose l=6 and r=10. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxnzyx).
• Choose l=1 and r=9. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
  • After this operation, S = XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

(((()))(()))(())

Sample Output 3

The final outcome may be an empty string.

Sample Input 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

Sample Output 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve

Problem Statement

Beware the special input format and the smaller memory limit than usual.

There is an undirected graph with vertices 1, 2, \dots, N, initially without edges.
You need to process the following Q queries on this graph:

1 u v

Type 1: Add an edge between vertices u and v.
Before adding the edge, u and v belong to different connected components (i.e., the graph always remains a forest).

2 u v

Type 2: If there is a vertex adjacent to both u and v, report its vertex number; otherwise, report 0.
Given that the graph always remains a forest, the answer to this query is uniquely determined.

The queries are given in an encrypted form.
The original query is defined by three integers A, B, C, and the encrypted query is given as three integers a, b, c.
Let X_k be the answer to the k-th type-2 query. Define X_k = 0 for k = 0.
Restore A, B, C from the given a, b, c as follows:

• Let l be the number of type-2 queries given before this query (not counting the query itself). Then, use the following:
  • A = 1 + (((a \times (1+X_l)) \mod 998244353) \mod 2)
  • B = 1 + (((b \times (1+X_l)) \mod 998244353) \mod N)
  • C = 1 + (((c \times (1+X_l)) \mod 998244353) \mod N)

Constraints

• All input values are integers.
• 2 \le N \le 10^5
• 1 \le Q \le 10^5
• 1 \le u < v \le N
• 0 \le a,b,c < 998244353

Sample Input 1

6 12
143209915 123840720 97293110
89822758 207184717 689046893
67757230 270920641 26993265
952858464 221010240 871605818
730183361 147726243 445163345
963432357 295317852 195433903
120904472 106195318 615645575
817920568 27584394 770578609
38727673 250957656 506822697
139174867 566158852 412971999
205467538 606353836 855642999
159292205 319166257 51234344

Sample Output 1

0
2
0
2
6
0
1

After decrypting all queries, the input is as follows:

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

This input has a 6-vertex graph and 12 queries.

• The first query is 2 1 3.
  • No vertex is adjacent to both vertex 1 and vertex 3, so report 0.
• The second query is 1 2 6.
  • Add an edge between vertices 2 and 6.
• The third query is 1 2 4.
  • Add an edge between vertices 2 and 4.
• The fourth query is 1 1 3.
  • Add an edge between vertices 1 and 3.
• The fifth query is 2 4 6.
  • The vertex adjacent to both vertices 4 and 6 is vertex 2.
• The sixth query is 2 1 4.
  • No vertex is adjacent to both vertices 1 and 4, so report 0.
• The seventh query is 1 5 6.
  • Add an edge between vertices 5 and 6.
• The eighth query is 1 1 2.
  • Add an edge between vertices 1 and 2.
• The ninth query is 2 1 4.
  • The vertex adjacent to both vertices 1 and 4 is vertex 2.
• The tenth query is 2 2 5.
  • The vertex adjacent to both vertices 2 and 5 is vertex 6.
• The eleventh query is 2 3 4.
  • No vertex is adjacent to both vertices 3 and 4, so report 0.
• The twelfth query is 2 2 3.
  • The vertex adjacent to both vertices 2 and 3 is vertex 1.

Sample Input 2

2 1
377373366 41280240 33617925

Sample Output 2

The output may be empty.