Problem Statement

You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.

Constraints

• S is a string of length 3 consisting of lowercase English letters.

Sample Input 1

pop

Sample Output 1

o

o occurs only once in pop.

Sample Input 2

abc

Sample Output 2

a

a, b, and c occur once each in abc, so you may print any of them.

Sample Input 3

xxx

Sample Output 3

-1

No character occurs only once in xxx.

Problem Statement

N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.

The admissions are determined as follows.

1. X examinees with the highest math scores are admitted.
2. Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
3. Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
4. Those examinees who are not admitted yet are rejected.

Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.

Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.

Constraints

• All values in input are integers.
• 1 \le N \le 1000
• 0 \le X,Y,Z \le N
• 1 \le X+Y+Z \le N
• 0 \le A_i,B_i \le 100

Sample Input 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

Sample Output 1

1
4
5

• First, 1 examinee with the highest math score is admitted.
  • Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
• Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
  • Obviously, it does not affect the admissions.
• Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
  • First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
  • Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.

Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.

Sample Input 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

Sample Output 2

1
2
3
4
5

All examinees may be admitted.

Sample Input 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

Sample Output 3

2
4
5
6
7
8
11
14
15

Problem Statement

Takahashi has a red jewel of level N. (He has no other jewels.)
Takahashi can do the following operations any number of times.

• Convert a red jewel of level n (n is at least 2) into "a red jewel of level (n-1) and X blue jewels of level n".
• Convert a blue jewel of level n (n is at least 2) into "a red jewel of level (n-1) and Y blue jewels of level (n-1)".

Takahashi wants as many blue jewels of level 1 as possible. At most, how many blue jewels of level 1 can he obtain by the operations?

Constraints

• 1 \leq N \leq 10
• 1 \leq X \leq 5
• 1 \leq Y \leq 5
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

12

Takahashi can obtain 12 blue jewels of level 1 by the following conversions.

• First, he converts a red jewel of level 2 into a red jewel of level 1 and 3 blue jewels of level 2.
  • After this operation, Takahashi has 1 red jewel of level 1 and 3 blue jewels of level 2.
• Next, he repeats the following conversion 3 times: converting a blue jewel of level 2 into a red jewel of level 1 and 4 blue jewels of level 1.
  • After these operations, Takahashi has 4 red jewels of level 1 and 12 blue jewels of level 1.
• He cannot perform a conversion anymore.

He cannot obtain more than 12 blue jewels of level 1, so the answer is 12.

Sample Input 2

1 5 5

Sample Output 2

0

Takahashi may not be able to obtain a blue jewel of level 1.

Sample Input 3

10 5 5

Sample Output 3

3942349900

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There is a deck consisting of N face-down cards with an integer from 1 through N written on them. The integer on the i-th card from the top is P_i.

Using this deck, you will perform N moves, each consisting of the following steps:

• Draw the topmost card from the deck. Let X be the integer written on it.
• Stack the drawn card, face up, onto the card with the smallest integer among the face-up topmost cards on the table with an integer greater than or equal to X written on them. If there is no such card on the table, put the drawn card on the table, face up, without stacking it onto any card.
• Then, if there is a pile consisting of K face-up cards on the table, eat all those cards. The eaten cards all disappear from the table.

For each card, find which of the N moves eats it. If the card is not eaten until the end, report that fact.

Constraints

• All values in input are integers.
• 1 \le K \le N \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N) (i.e. a sequence obtained by rearranging (1,2,\dots,N)).

Sample Input 1

5 2
3 5 2 1 4

Sample Output 1

4
3
3
-1
4

In this input, P=(3,5,2,1,4) and K=2.

• In the 1-st move, the card with 3 written on it is put on the table, face up, without stacked onto any card.
• In the 2-nd move, the card with 5 written on it is put on the table, face up, without stacked onto any card.
• In the 3-rd move, the card with 2 written on it is stacked, face up, onto the card with 3 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 2 and 3 from the top are written, so these cards are eaten.
• In the 4-th move, the card with 1 written on it is stacked, face up, onto the card with 5 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 1 and 5 from the top are written, so these cards are eaten.
• In the 5-th move, the card with 4 written on it is put on the table, face up, without stacked onto any card.
• The card with 4 written on it was not eaten until the end.

Sample Input 2

5 1
1 2 3 4 5

Sample Output 2

1
2
3
4
5

If K=1, every card is eaten immediately after put on the table within a single move.

Sample Input 3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

Sample Output 3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

• S is a contiguous subsequence of the sequence (1,2,3,..., M).
• For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

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

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

• (1,2)
• (1,2,3)
• (2,3,4)
• (3,4,5)
• (1,2,3,4)
• (2,3,4,5)
• (1,2,3,4,5)

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

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

Sample Output 3

0 0 1 2 4 4 3 2 1

Problem Statement

We have a simple undirected graph G with (S+T) vertices and M edges. The vertices are numbered 1 through (S+T), and the edges are numbered 1 through M. Edge i connects Vertices u_i and v_i.
Here, vertex sets V_1 = \lbrace 1, 2,\dots, S\rbrace and V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace are both independent sets.

A cycle of length 4 is called a 4-cycle.
If G contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.
If G does not contain a 4-cycle, print -1.

Constraints

• 2 \leq S \leq 3 \times 10^5
• 2 \leq T \leq 3000
• 4 \leq M \leq \min(S \times T,3 \times 10^5)
• 1 \leq u_i \leq S
• S + 1 \leq v_i \leq S + T
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1 2 4 5

There are edges between Vertices 1 and 4, 4 and 2, 2 and 5, and 5 and 1, so Vertices 1, 2, 4, and 5 form a 4-cycle. Thus, 1, 2, 4, and 5 should be printed.
The vertices may be printed in any order. Besides the Sample Output, 2 5 1 4 is also considered correct, for example.

Sample Input 2

3 2 4
1 4
1 5
2 5
3 5

Sample Output 2

-1

Some inputs may give G without a 4-cycle.

Sample Input 3

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

Sample Output 3

1 7 2 9

Problem Statement

We have an N \times N grid. The square at the i-th row from the top and j-th column from the left in this grid is called (i,j).
Each square of the grid has at most one piece.
The state of the grid is given by N strings S_i:

• if the j-th character of S_i is O, then (i,j) has a piece on it;
• if the j-th character of S_i is X, then (i,j) has no piece on it.

You are given an integer M. Using this M, we define that a piece P placed at (s,t) covers a square (u,v) if all of the following conditions are satisfied:

• s \le u \le N
• t \le v \le N
• (u - s) + \frac{(v - t)}{2} < M

For each of Q squares (X_i,Y_i), find how many pieces cover the square.

Constraints

• N, M, X_i, Y_i, and Q are integers.
• 1 \le N \le 2000
• 1 \le M \le 2 \times N
• S_i consists of O and X.
• 1 \le Q \le 2 \times 10^5
• 1 \le X_i,Y_i \le N

Sample Input 1

4 2
OXXX
XXXX
XXXX
XXXX
6
1 1
1 4
2 2
2 3
3 1
4 4

Sample Output 1

1
1
1
0
0
0

Only Square (1,1) contains a piece, which covers the following # squares:

####
##..
....
....

Sample Input 2

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

Sample Output 2

1
6
12
8
25

Sample Input 3

8 5
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
OXXOXXOX
XOXXOXOX
XOOXOOXO
OXOOXOXO
6
7 2
8 1
4 5
8 8
3 4
1 7

Sample Output 3

5
3
9
14
5
3

Problem Statement

There are N balls numbered 1 through N. Ball i is painted in Color a_i.

For a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N), let us define C(P) as follows:

• The number of pairs of adjacent balls with different colors when Balls P_1, P_2, \dots, P_N are lined up in a row in this order.

Let S_N be the set of all permutations of (1, 2, \dots, N). Also, let us define F(k) by:

Enumerate F(1), F(2), \dots, F(M).

Constraints

• 2 \leq N \leq 2.5 \times 10^5
• 1 \leq M \leq 2.5 \times 10^5
• 1 \leq a_i \leq N
• All values in input are integers.

Sample Input 1

3 4
1 1 2

Sample Output 1

8 12 20 36

Here is the list of all possible pairs of (P, C(P)).

• If P=(1,2,3), then C(P) = 1.
• If P=(1,3,2), then C(P) = 2.
• If P=(2,1,3), then C(P) = 1.
• If P=(2,3,1), then C(P) = 2.
• If P=(3,1,2), then C(P) = 1.
• If P=(3,2,1), then C(P) = 1.

We may obtain the answers by assigning these values into F(k). For instance, F(1) = 1^1 + 2^1 + 1^1 + 2^1 + 1^1 + 1^1 = 8.

Sample Input 2

2 1
1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

30481920 257886720 199419134 838462446 196874334