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 of length exactly 9 consisting of digits. One but all digits from 0 to 9 appear exactly once in S.

Print the only digit missing in S.

Constraints

• S is a string of length 9 consisting of digits.
• All characters in S are distinct.

Sample Input 1

023456789

Sample Output 1

1

The string 023456789 only lacks 1. Thus, 1 should be printed.

Sample Input 2

459230781

Sample Output 2

6

The string 459230781 only lacks 6. Thus, 6 should be printed.

Note that the digits in the string may not appear in increasing order.

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

• 1 \leq N \leq M \leq 100
• S is a string of length N consisting of lowercase English letters.
• T is a string of length M consisting of lowercase English letters.

Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.

Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.

Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.

Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

Problem Statement

You are given two positive integers N and M.

Let X = \displaystyle\sum_{i = 0}^{M} N^i. If X \leq 10^9, print the value of X. If X > 10^9, print inf.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 100
• All input values are integers.

Sample Input 1

7 3

Sample Output 1

400

X = 1 + 7 + 49 + 343 = 400. Since 400 \leq 10^9, print 400.

Sample Input 2

1000000 2

Sample Output 2

inf

X = 1000001000001 > 10^9, so print inf.

Sample Input 3

999999999 1

Sample Output 3

1000000000

Sample Input 4

998244353 99

Sample Output 4

inf

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

• You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
• The test result is represented by a single English letter R_i.
  • R_i = o means that Door X opened in the i-th test.
  • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

• N, M, K, C_i, and A_{i,j} are integers.
• 1 \le K \le N \le 15
• 1 \le M \le 100
• 1 \le C_i \le N
• 1 \le A_{i,j} \le N
• A_{i,j} \neq A_{i,k} if j \neq k.
• R_i is o or x.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

• In the first test, keys 1, 2, 3 were used, and Door X opened.
• In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

• Key 1 is real, key 2 is a dummy, and key 3 is real.
• Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

You will perform an operation Q times on the string S. The i-th operation (1\leq i\leq Q) is represented by a pair of characters (c _ i,d _ i), which corresponds to the following operation:

• Replace all occurrences of the character c _ i in S with the character d _ i.

Print the string S after all operations are completed.

Constraints

• 1\leq N\leq2\times10^5
• S is a string of length N consisting of lowercase English letters.
• 1\leq Q\leq2\times10^5
• c _ i and d _ i are lowercase English letters (1\leq i\leq Q).
• N and Q are integers.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

S changes as follows: atcoder → atcodea → aecodea → aecovea → recover. For example, in the fourth operation, all occurrences of a in S={}aecovea (the first and seventh characters) are replaced with r, resulting in S={}recover.

After all operations are completed, S={}recover, so print recover.

Sample Input 2

3
abc
4
a a
s k
n n
z b

Sample Output 2

abc

There may be operations where c _ i=d _ i or S does not contain c _ i.

Sample Input 3

34
supercalifragilisticexpialidocious
20
g c
l g
g m
c m
r o
s e
a a
o f
f s
e t
t l
d v
p k
v h
x i
h n
n j
i r
s i
u a

Sample Output 3

laklimamriiamrmrllrmlrkramrjimrial

Problem Statement

A souvenir shop at AtCoder Land sells N boxes.

The boxes are numbered 1 to N, and box i has a price of A_i yen and contains A_i pieces of candy.

Takahashi wants to buy M out of the N boxes and give one box each to M people named 1, 2, \ldots, M.

Here, he wants to buy boxes that can satisfy the following condition:

• For each i = 1, 2, \ldots, M, person i is given a box containing at least B_i pieces of candy.

Note that it is not allowed to give more than one box to a single person or to give the same box to multiple people.

Determine whether it is possible to buy M boxes that can satisfy the condition, and if it is possible, find the minimum total amount of money Takahashi needs to pay.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4 2
3 4 5 4
1 4

Sample Output 1

7

Takahashi can buy boxes 1 and 4, and give box 1 to person 1 and box 4 to person 2 to satisfy the condition.

In this case, he needs to pay 7 yen in total, and it is impossible to satisfy the condition by paying less than 7 yen, so print 7.

Sample Input 2

3 3
1 1 1
1000000000 1000000000 1000000000

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

19

Problem Statement

We have an integer sequence A and a notebook. The notebook has 10^9 pages.

You are given Q queries. Each query is of one of the following four kinds:

ADD x: append an integer x to the tail of A.

DELETE: remove the last term of A if A is not empty; do nothing otherwise.

SAVE y: erase the sequence recorded on the y-th page of the notebook, and record the current A onto the y-th page.

LOAD z: replace A with the sequence recorded on the z-th page of the notebook.

Initially, A is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process Q queries successively in the given order and print the last term of A after processing each query.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• 1 \leq Q \leq 5 \times 10^5
• 1 \leq x, y, z \leq 10^9
• Q, x, y, and z are integers.
• Each of the given queries is of one of the four kinds in the Problem Statement.

Sample Input 1

11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

Sample Output 1

3 3 4 4 3 -1 -1 4 4 -1 4

Initially, A is an empty sequence, so A = (), and an empty sequence is recorded on each page of the notebook.

• By the 1-st query, 3 is appended to the tail of A, resulting in A = (3).
• By the 2-nd query, the sequence recorded on the 1-st page of the notebook becomes (3). It remains that A = (3).
• By the 3-rd query, 4 is appended to the tail of A, resulting in A = (3, 4).
• By the 4-th query, the sequence recorded on the 2-nd page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 5-th query, A is replaced by (3), which is recorded on the 1-st page of the notebook, resulting in A = (3).
• By the 6-th query, the last term of A is removed, resulting in A = ().
• By the 7-th query, nothing happens because A is already empty. It remains that A = ().
• By the 8-th query, A is replaced by (3,4), which is recorded on the 2-nd page of the notebook, resulting in A = (3, 4).
• By the 9-th query, the sequence recorded on the 1-st page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 10-th query, A is replaced by (), which is recorded on the 3-rd page of the notebook, resulting in A = ().
• By the 11-th query, A is replaced by (3, 4), which is recorded on the 1-st page of the notebook, resulting in A = (3, 4).

Sample Input 2

21
ADD 4
ADD 3
DELETE
ADD 10
LOAD 7
SAVE 5
SAVE 5
ADD 4
ADD 4
ADD 5
SAVE 5
ADD 2
DELETE
ADD 1
SAVE 5
ADD 7
ADD 8
DELETE
ADD 4
DELETE
LOAD 5

Sample Output 2

4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1

Problem Statement

You are given a tree with N vertices. For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i and has a weight w_i.

Consider choosing some of the N-1 edges (possibly none or all). Here, for each i = 1, 2, \ldots, N, one may choose at most d_i edges incident to Vertex i. Find the maximum possible total weight of the chosen edges.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq u_i, v_i \leq N
• -10^9 \leq w_i \leq 10^9
• d_i is a non-negative integer not exceeding the degree of Vertex i.
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

28

If you choose the 1-st, 2-nd, 5-th, and 6-th edges, the total weight of those edges is 8 + 9 + 8 + 3 = 28. This is the maximum possible.

Sample Input 2

20
0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2
4 9 583
4 6 -431
5 9 325
17 6 131
17 2 -520
2 16 696
5 7 662
17 15 845
7 8 307
13 7 849
9 19 242
20 6 909
7 11 -775
17 18 557
14 20 95
18 10 646
4 3 -168
1 3 -917
11 12 30

Sample Output 2

2184