Problem Statement

AtCoder Grand Contest (AGC), a regularly held contest with a world authority, has been held 54 times.

Just like the 230-th ABC ― the one you are in now ― is called ABC230, the N-th AGC is initially named with a zero-padded 3-digit number N. (The 1-st AGC is AGC001, the 2-nd AGC is AGC002, ...)

However, the latest 54-th AGC is called AGC055, where the number is one greater than 54. Because AGC042 is canceled and missing due to the social situation, the 42-th and subsequent contests are assigned numbers that are one greater than the numbers of contests held. (See also the explanations at Sample Inputs and Outputs.)

Here is the problem: given an integer N, print the name of the N-th AGC in the format AGCXXX, where XXX is the zero-padded 3-digit number.

Constraints

• 1 \leq N \leq 54
• N is an integer.

Sample Input 1

42

Sample Output 1

AGC043

As explained in Problem Statement, the 42-th and subsequent AGCs are assigned numbers that are one greater than the numbers of contests.
Thus, the 42-th AGC is named AGC043.

Sample Input 2

19

Sample Output 2

AGC019

The 41-th and preceding AGCs are assigned numbers that are equal to the numbers of contests.
Thus, the answer is AGC019.

Sample Input 3

1

Sample Output 3

AGC001

As mentioned in Problem Statement, the 1-st AGC is named AGC001.
Be sure to pad the number with zeros into a 3-digit number.

Sample Input 4

50

Sample Output 4

AGC051

Problem Statement

You are given a string s consisting of two kinds of characters, 0 and 1. Print the string obtained by replacing 0 with 1 and 1 with 0 in s.

Constraints

• The length of s is between 1 and 10, inclusive.
• s consists of two kinds of characters, 0 and 1.

Sample Input 1

01

Sample Output 1

10

The 1-st character of s is 1, so the 1-st character to print is 0. The 2-nd character of s is 0, so the 2-nd character to print is 1.

Sample Input 2

1011

Sample Output 2

0100

Sample Input 3

100100001

Sample Output 3

011011110

Problem Statement

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

• 0 \leq S \leq 100
• 0 \leq T \leq 10000
• S and T are integers.

Sample Input 1

1 0

Sample Output 1

4

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

10

Sample Input 3

10 10

Sample Output 3

213

Sample Input 4

30 100

Sample Output 4

2471

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

• 1 \leq a \lt b \lt c \leq N
• There is an edge connecting Vertex a and Vertex b.
• There is an edge connecting Vertex b and Vertex c.
• There is an edge connecting Vertex c and Vertex a.

Constraints

• 3 \leq N \leq 100
• 1 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.

Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

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

Sample Output 3

4

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

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

You are given an integer W.
You are going to prepare some weights so that all of the conditions below are satisfied.

• The number of weights is between 1 and 300, inclusive.
• Each weight has a mass of positive integer not exceeding 10^6.
• Every integer between 1 and W, inclusive, is a good integer. Here, a positive integer n is said to be a good integer if the following condition is satisfied:
  • We can choose at most 3 different weights from the prepared weights with a total mass of n.

Print a combination of weights that satisfies the conditions.

Constraints

• 1 \leq W \leq 10^6
• W is an integer.

Sample Input 1

6

Sample Output 1

3
1 2 3

In the output above, 3 weights with masses 1, 2, and 3 are prepared.
This output satisfies the conditions. Especially, regarding the 3-rd condition, we can confirm that every integer between 1 and W, inclusive, is a good integer.

• If we choose only the 1-st weight, it has a total mass of 1.
• If we choose only the 2-nd weight, it has a total mass of 2.
• If we choose only the 3-rd weight, it has a total mass of 3.
• If we choose the 1-st and the 3-rd weights, they have a total mass of 4.
• If we choose the 2-nd and the 3-rd weights, they have a total mass of 5.
• If we choose the 1-st, the 2-nd, and the 3-rd weights, they have a total mass of 6.

Sample Input 2

12

Sample Output 2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.

Problem Statement

We have N cards. The i-th card (1 \leq i \leq N) has an integer A_i written on it.

Takahashi will choose any number of cards from these. However, for each i (1 \leq i \leq N - 1), at least one of the i-th and (i+1)-th cards must be chosen.

Find the following values.

• The maximum possible average of the integers written on the chosen cards
• The maximum possible median of the integers written on the chosen cards

Here, the median of the n integers is defined to be the \lceil \frac{n}{2} \rceil-th smallest of them, where \lceil x \rceil is the smallest integer not less than x.

Constraints

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

Sample Input 1

6
2 1 2 1 1 10

Sample Output 1

4
2

Choosing the 2-nd, 4-th, and 6-th cards makes the average of the written integers \frac{12}{3} = 4, which is the maximum possible.

Choosing the 1-st, 3-rd, 5-th, and 6-th cards makes the median of the written integers 2, which is the maximum possible.

Sample Input 2

7
3 1 4 1 5 9 2

Sample Output 2

5.250000000
4

For the average, your output may contain some degree of error: for example, the output 5.2491 is still considered correct. For the median, however, the exact value must be printed.

Problem Statement

You are given N, Q, and A=(A_1,\ldots,A_N).
Process Q queries, each of which is of one of the following two kinds:

• 1 x v: update A_x to v.
• 2 x: let B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j, and D_i=\sum_{j=1}^{i}C_j. Print D_x modulo 998244353.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq Q \leq 2\times10^5
• 0 \leq A_i \leq 10^9
• 1 \leq x \leq N
• 0 \leq v \leq 10^9
• All values in input are integers.

Sample Input 1

3 3
1 2 3
2 3
1 2 0
2 3

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.

When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0