Problem Statement

Takahashi, as an organizing staff member of an international conference, has been tasked with preparing invitation letters for the participants.

The invitation list contains N participants. The i-th participant (1 \leq i \leq N) has a name S_i and a title R_i registered. On the invitation, each participant's name is followed by an honorific determined by the following rules, separated by a space:

• For people whose title is teacher or doctor, the honorific sensei is appended.
• For people whose title is student or other, the honorific san is appended.

Furthermore, co-organizer Aoki has requested that "the order of the list be adjusted." Specifically, the participants are divided into the following two groups, and all members of Group A are placed before all members of Group B:

• Group A: People whose title is teacher or doctor
• Group B: People whose title is student or other

Within each group, the order given in the input (ascending order of i) is preserved. That is, the relative order of participants belonging to the same group must match their relative order in the input.

For the rearranged list, output each participant's name and honorific separated by a space, in order. Note that the honorific to output is not the title itself, but sensei or san as determined by the rules above.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S_i is a string of length between 1 and 20 inclusive, consisting only of lowercase English letters.
• R_i is one of teacher, doctor, student, other.
• There may be multiple participants with the same name. There may also be multiple participants with both the same name and the same title.

Sample Input 1

4
alice student
bob teacher
carol other
dave doctor

Sample Output 1

bob sensei
dave sensei
alice san
carol san

Sample Input 2

3
emma teacher
frank doctor
grace student

Sample Output 2

emma sensei
frank sensei
grace san

Sample Input 3

10
akira other
ben doctor
chika student
diana teacher
eri doctor
felix other
gina teacher
hiro student
iris other
jack doctor

Sample Output 3

ben sensei
diana sensei
eri sensei
gina sensei
jack sensei
akira san
chika san
felix san
hiro san
iris san

Sample Input 4

20
alice student
bob teacher
carol doctor
dave other
emma student
frank doctor
grace teacher
henry other
iris doctor
jack student
kate teacher
leo other
mia student
noah doctor
olivia teacher
paul other
quinn doctor
ruby student
sam teacher
tina other

Sample Output 4

bob sensei
carol sensei
frank sensei
grace sensei
iris sensei
kate sensei
noah sensei
olivia sensei
quinn sensei
sam sensei
alice san
dave san
emma san
henry san
jack san
leo san
mia san
paul san
ruby san
tina san

Sample Input 5

1
a other

Sample Output 5

a san

Problem Statement

Takahashi is in charge of managing meeting room reservations at his company.

The meeting room is available during the interval [0, T], from time 0 to time T.

There are N reservations for the meeting room today. The i-th reservation starts at time S_i and ends at time E_i. That is, the i-th reservation occupies the half-open interval [S_i, E_i). The time intervals of the reservations do not overlap with each other. However, the reservations are not necessarily given in ascending order of start time.

Among the available time [0, T], the portions not used by any reservation are called free time. Takahashi wants to secure the longest possible continuous free time for a meeting that was suddenly scheduled.

Find the length of the longest continuous free time in today's meeting room. If there is no free time, output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 0 \leq S_i < E_i \leq T (1 \leq i \leq N)
• The time intervals of the reservations do not overlap. That is, if i \neq j, then the half-open intervals [S_i, E_i) and [S_j, E_j) have no common part.
• All inputs are integers.

Sample Input 1

3 10
1 3
5 6
8 9

Sample Output 1

2

Sample Input 2

5 100
0 10
20 35
40 60
70 85
95 100

Sample Output 2

10

Sample Input 3

4 1000000000
100000000 200000000
300000000 400000000
600000000 700000000
900000000 950000000

Sample Output 3

200000000

Problem Statement

Takahashi is in charge of scoring at a darts tournament.

In this tournament, Aoki throws darts a total of N times. For the i-th throw, the distance D_i from the center of the dartboard to where the dart lands is recorded.

This darts tournament has a special scoring rule. On the dartboard, M "bonus areas" are defined. The j-th bonus area is a ring-shaped region consisting of all points whose distance from the center of the dartboard is at least L_j and at most R_j. Note that bonus areas may overlap with each other.

The score for each throw is calculated as follows:

• If the distance D_i from the center to where the dart lands is contained in at least one of the M bonus areas (that is, if there exists at least one j such that L_j \leq D_i \leq R_j), the score for that throw is 2 \times D_i. Even if the dart is contained in multiple bonus areas simultaneously, the score remains 2 \times D_i.
• If it is not contained in any bonus area, the score for that throw is D_i.

Given the results of Aoki's N throws, calculate the total score on behalf of Takahashi.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq L_j \leq R_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

3 2
5 10 15
3 7
12 20

Sample Output 1

50

Sample Input 2

4 1
1 2 3 4
2 3

Sample Output 2

15

Sample Input 3

5 3
0 100 50 75 200
0 60
40 80
150 300

Sample Output 3

750

Sample Input 4

10 4
1000000000 500000000 0 999999999 250000000 750000000 100 200 300 400
0 100
999999998 1000000000
200 300
500000000 750000000

Sample Output 4

6750001598

Sample Input 5

1 1
0
0 0

Sample Output 5

0

Problem Statement

Takahashi is exploring a maze represented by a grid with H rows and W columns.

He needs to reach the goal G from the starting point S.

Each square contains one of the following characters:

• S : Starting point (passable)
• G : Goal (passable)
• O : Normal square (passable, uppercase letter O)
• B : Wall (impassable)
• P : Trap square (passable)

Takahashi starts on the S square with a cumulative damage of 0.

In one move, he can advance from his current square to an adjacent square in one of the four directions (up, down, left, right). However, he cannot move outside the grid or onto a B square. He may pass through the same square any number of times.

When the destination square is P, the cumulative damage increases by 1 each time he enters that square. Even for the same P square, damage is added every time he enters it. Entering S, G, or O squares does not increase the damage.

The exploration ends immediately when Takahashi reaches the G square.

If a path from S to G exists, output the minimum cumulative damage upon reaching the goal.

If it is impossible to reach G regardless of how he moves, output -1.

Constraints

• 1 \leq H \leq 2000
• 1 \leq W \leq 2000
• H \times W \leq 10^6
• H, W are integers
• A_i \, (1 \leq i \leq H) is a string of length W consisting of S, G, O, B, P
• The entire input contains exactly one S and exactly one G

Sample Input 1

3 5
SPOOG
BBBBO
OOOOO

Sample Output 1

1

Sample Input 2

4 5
SOBBG
OOBBB
BBBBB
POOOO

Sample Output 2

-1

Sample Input 3

8 10
SOOPBPOOOO
BBOPBOBBBO
OOOPOOPOOO
OBBBBBBPOB
OOPPPBOOOB
BOBOPBOBPO
OPOOPOOOPO
BBBBOBBBPG

Sample Output 3

3

Sample Input 4

12 16
SPOOBPOOOOBOPPPO
OBBOOPOBOOOOBOPO
OPOPBOOOBBOPOOBO
OOBOPPBOOOOPBOOO
OPPOBOOOPBBBOOPO
OBOPOOBOOOPOPBOO
OOOOPBBBOBOOOPPO
OPBBOOPOOOOBOBOO
OOPOBBOOPPOOBBPO
OBOPOOOPBOBOOOOO
OPPBBOOOOPPOBPOO
OOOOPOOOOPPOOOOG

Sample Output 4

1

Sample Input 5

1 2
SG

Sample Output 5

0

Problem Statement

Takahashi is cleaning up a card game. There are N cards lined up in a row from left to right on a table. The i-th card from the left is called "card i". Card i has an integer A_i written on it.

Takahashi will organize these cards by dividing them into several piles. The piles must be created according to the following rules:

• Process card 1, card 2, \ldots, card N in this order, one by one (the order cannot be changed).
• For each card, choose one of the following operations:
• Create a new pile and place the card on it.
• Place the card on top of an already existing pile. However, if the number written on the current top card of that pile is x and the number on the card to be placed is y, then x \geq y must hold.

Under these rules, the numbers written on the cards in each pile will be monotonically non-increasing from bottom to top.

Takahashi wants to minimize the number of piles.

Furthermore, for each card, Takahashi wants to record "which card is directly below it". The card directly below card i refers to the card that was at the top of the pile at the moment card i was placed on top of that existing pile. If card i was placed to start a new pile (i.e., it is at the bottom of the pile), there is no card directly below it.

For each card i (i = 1, 2, \ldots, N), we define the value B_i as follows:

• If there is no card directly below card i (i.e., it is at the bottom of a pile), B_i = 0.
• If the card directly below card i is card j, B_i = j.

Among all ways of piling the cards that minimize the number of piles, find one way that maximizes B_1 + B_2 + \cdots + B_N.

Let K be the minimum number of piles. Output K and B_1, B_2, \ldots, B_N.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 2 2

Sample Output 1

2
0 1 0 3 4

Sample Input 2

4
1 2 3 4

Sample Output 2

4
0 0 0 0

Sample Input 3

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

Sample Output 3

4
0 0 1 3 4 0 5 6 8 9 10 0

Sample Input 4

30
10 20 15 15 30 25 5 18 18 17 40 35 34 10 9 50 45 45 44 1 60 59 20 19 70 2 2 80 79 78

Sample Output 4

8
0 0 2 3 0 5 4 6 8 9 0 11 12 13 14 0 16 17 18 19 0 21 22 23 0 25 26 0 28 29

Sample Input 5

1
1000000000

Sample Output 5

1
0