Problem Statement

You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)

Constraints

• S is a string of length between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

abcdaxayz

Sample Output 1

7

a appears three times in S. The last occurrence is at index 7, so you should print 7.

Sample Input 2

bcbbbz

Sample Output 2

-1

a does not appear in S, so you should print -1.

Sample Input 3

aaaaa

Sample Output 3

5

Problem Statement

Takahashi and Aoki played N games. You are given a string S of length N, representing the results of these games. Takahashi won the i-th game if the i-th character of S is T, and Aoki won that game if it is A.

The overall winner between Takahashi and Aoki is the one who won more games than the other. If they had the same number of wins, the overall winner is the one who reached that number of wins first. Find the overall winner: Takahashi or Aoki.

Constraints

• 1\leq N \leq 100
• N is an integer.
• S is a string of length N consisting of T and A.

Sample Input 1

5
TTAAT

Sample Output 1

T

Takahashi won three games, and Aoki won two. Thus, the overall winner is Takahashi, who won more games.

Sample Input 2

6
ATTATA

Sample Output 2

T

Both Takahashi and Aoki won three games. Takahashi reached three wins in the fifth game, and Aoki in the sixth game. Thus, the overall winner is Takahashi, who reached three wins first.

Sample Input 3

1
A

Sample Output 3

A

Problem Statement

You are given a positive integer X.

Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.

Constraints

• 1\leq X < 10^5
• X is an integer.

Sample Input 1

903

Sample Output 1

309

There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.

Sample Input 2

432

Sample Output 2

234

Sample Input 3

100

Sample Output 3

100

Problem Statement

People 1,2,\dots,N (where N is odd) conducted M votes where each person chooses either 0 or 1.
Each person's vote for each round is given as N strings S_1,S_2,\dots,S_N of length M consisting of 0 and 1, where the j-th character of S_i represents person i's vote content for the j-th vote.

In each vote, people who were in the minority receive 1 point.
More precisely, points are given according to the following rules:

• Suppose x people chose 0 and y people chose 1 in that vote.
  • If x=0 or y=0, everyone receives 1 point for that vote.
  • Otherwise, if x<y, only people who voted 0 in that vote receive 1 point.
  • Otherwise, only people who voted 1 in that vote receive 1 point.
  • Note that since N is odd, x=y never occurs.

After finishing M votes, find all people who have the highest total score from those votes.

Constraints

• N is an odd number satisfying 1 \le N \le 99.
• M is an integer satisfying 1 \le M \le 100.
• S_i is a string of length M consisting of 0 and 1.

Sample Input 1

3 5
11100
10101
01110

Sample Output 1

2 3

In this case, three people conducted five votes.

• In the 1st vote, person 1 voted 1, person 2 voted 1, person 3 voted 0. Thus, only person 3 receives 1 point.
• In the 2nd vote, person 1 voted 1, person 2 voted 0, person 3 voted 1. Thus, only person 2 receives 1 point.
• In the 3rd vote, person 1 voted 1, person 2 voted 1, person 3 voted 1. Thus, everyone receives 1 point.
• In the 4th vote, person 1 voted 0, person 2 voted 0, person 3 voted 1. Thus, only person 3 receives 1 point.
• In the 5th vote, person 1 voted 0, person 2 voted 1, person 3 voted 0. Thus, only person 2 receives 1 point.

As a result, person 1 received a total of 1 points, person 2 received a total of 3 points, and person 3 received a total of 3 points.
Therefore, persons 2 and 3 have the highest total score. Output these in ascending order of person number.

Sample Input 2

5 4
0000
0000
0000
0000
0000

Sample Output 2

1 2 3 4 5

Sample Input 3

7 8
11010011
01000000
01111100
10111000
10011110
10100101
10010110

Sample Output 3

1 2 3

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

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

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

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

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.

You are given M pieces of information in the following form:

• From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.

Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i, B_i \leq N
• A_i \neq B_i
• -10^9 \leq X_i,Y_i \leq 10^9
• All input values are integers.
• The given information is consistent.

Sample Input 1

3 2
1 2 2 1
1 3 -1 -2

Sample Output 1

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 2

3 2
2 1 -2 -1
2 3 -3 -3

Sample Output 2

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

Sample Output 3

0 0
0 0
0 0
undecidable
undecidable

The same piece of information may be given multiple times, and multiple people may be at the same coordinates.

Problem Statement

Takahashi is about to play a game where he fights N monsters in order. Initially, Takahashi's health is H and his magic power is M.

For the i-th monster he fights, he can choose one of the following actions:

• Fight without using magic. This can only be chosen when his health is at least A_i, and his health decreases by A_i and the monster is defeated.
• Fight using magic. This can only be chosen when his magic power is at least B_i, and his magic power decreases by B_i and the monster is defeated.

The game ends when all N monsters are defeated or when he cannot take any action. What is the maximum number of monsters he can defeat before the game ends?

Constraints

• 1 \leq N \leq 3000
• 1 \leq H,M \leq 3000
• 1 \leq A_i,B_i \leq 3000
• All input values are integers.

Sample Input 1

4 10 14
5 8
5 6
7 9
99 99

Sample Output 1

3

By taking the following actions, Takahashi can defeat 3 monsters before the game ends.

• Initially, his health is 10 and his magic power is 14.
• Fight the 1st monster without using magic. His health decreases by 5, becoming health 5 and magic power 14.
• Fight the 2nd monster without using magic. His health decreases by 5, becoming health 0 and magic power 14.
• Fight the 3rd monster using magic. His magic power decreases by 9, becoming health 0 and magic power 5.
• For the 4th monster, he cannot choose either action, so the game ends.

Sample Input 2

3 3000 3000
3 3
3 3
3 3

Sample Output 2

3

He may be able to defeat all monsters.

Sample Input 3

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

Sample Output 3

9

Problem Statement

There are N scaffolds numbered from 1 to N arranged in a line. The height of scaffold i(1 \leq i \leq N) is H_i.

Takahashi decides to play a game of moving on the scaffolds. Initially, he freely chooses an integer i(1 \leq i \leq N) and gets on scaffold i.

When he is on scaffold i at some point, he can choose an integer j(1 \leq j \leq N) satisfying the following condition and move to scaffold j:

• H_j \leq H_i - D and 1 \leq |i-j| \leq R.

Find the maximum number of moves he can make when he repeats moving until he can no longer move.

Constraints

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

Sample Input 1

5 2 1
5 3 1 4 2

Sample Output 1

2

Takahashi initially gets on scaffold 1 and can move between the scaffolds as follows:

• First move: Since H_2 \leq H_1 -D and |2-1| \leq R, he can move to scaffold 2. Move from scaffold 1 to scaffold 2.
• Second move: Since H_3 \leq H_2 -D and |3-2| \leq R, he can move to scaffold 3. Move from scaffold 2 to scaffold 3.
• Since the height of scaffold 3 is 1, he can no longer move.

As shown above, he can move 2 times. Also, no matter how he chooses the scaffolds to move to, he cannot move 3 or more times. Therefore, output 2.

Sample Input 2

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

Sample Output 2

3