Problem Statement

A single-elimination tournament is held with N players. Here, N is a power of 2.

Each player is assigned a number from 1 to N, and the strength of player i is S_i. All players have distinct strengths, and in any match, the player with the greater strength value always wins. A player who loses is eliminated from the tournament, and matches continue until a single champion is determined.

Since N is a power of 2, the tournament consists of exactly R = \log_2 N rounds. The matchups for each round are determined as follows:

• Round 1: Player 2i-1 and player 2i play against each other. This is called match i of round 1 (i = 1, 2, \ldots, N/2).
• Round r (r \geq 2): The winner of match 2j-1 and the winner of match 2j from the previous round (round r-1) play against each other. This is called match j of round r (j = 1, 2, \ldots, N/2^r).

Match numbers within each round are numbered starting from 1 and are reassigned for each round. In round R, there is only one match, and its winner is the champion.

For each player, determine the round number in which that player is defeated. However, since the champion is never defeated, output 0 for the champion. Rounds are numbered starting from 1.

Constraints

• 2 \leq N \leq 2^{19}
• N is a power of 2
• 1 \leq S_i \leq N (1 \leq i \leq N)
• All S_i are distinct
• All input values are integers

Sample Input 1

4
1 4 3 2

Sample Output 1

1 0 2 1

Sample Input 2

8
8 1 6 2 5 3 7 4

Sample Output 2

0 1 2 1 2 1 3 1

Sample Input 3

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

Sample Output 3

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

Sample Input 4

32
32 1 24 9 16 17 8 25 31 2 23 10 15 18 7 26 30 3 22 11 14 19 6 27 29 4 21 12 13 20 5 28

Sample Output 4

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

Sample Input 5

2
1 2

Sample Output 5

1 0

Problem Statement

Takahashi works part-time at an orchard. In this orchard, N fruit trees are lined up in a row, and the i-th tree from the left has A_i fruits.

Takahashi is about to perform the harvest. He uses a special cart for harvesting, but since this cart can only move along a contiguous section of the row of trees, he must choose exactly K consecutive trees and harvest all the fruits from those K trees. More precisely, he chooses an integer l (1 \leq l \leq N - K + 1) and harvests all the fruits from the K trees starting from the l-th tree to the (l + K - 1)-th tree from the left.

Takahashi wants to maximize the number of fruits he can harvest. Find the maximum number of fruits that can be harvested when the K consecutive trees are chosen optimally.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5 3
2 5 3 8 1

Sample Output 1

16

Sample Input 2

7 2
10 4 8 6 15 3 9

Sample Output 2

21

Sample Input 3

10 4
100 250 180 320 90 410 275 150 380 200

Sample Output 3

1215

Problem Statement

Takahashi has come to a street of festival stalls. There are N stalls on the street, and each stall sells one type of food item.

Takahashi has M yen. The food at stall i (1 \leq i \leq N) costs T_i yen, and purchasing it gives a satisfaction of P_i. For each stall, Takahashi chooses either to purchase the food or not. He cannot purchase more than one item from the same stall. It is also allowed to not purchase food from any stall at all. In that case, the total satisfaction is 0.

Takahashi wants to choose a combination of stalls such that the total cost of the purchased food items does not exceed his budget of M yen, and he wants to maximize the total satisfaction.

Find the maximum total satisfaction.

Constraints

• 1 \leq N \leq 15
• 1 \leq M \leq 10^4
• 1 \leq T_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 10
3 5
4 6
5 8

Sample Output 1

14

Sample Input 2

4 5
3 4
3 5
6 10
2 3

Sample Output 2

8

Sample Input 3

8 50
12 20
15 25
10 18
8 12
20 35
5 8
18 30
7 10

Sample Output 3

86

Sample Input 4

15 5000
300 450
1200 1800
450 700
800 1100
150 200
2000 3500
600 950
350 500
900 1400
1100 1600
250 380
700 1050
500 780
400 620
1500 2200

Sample Output 4

8160

Sample Input 5

1 1
2 100

Sample Output 5

0

Problem Statement

Takahashi has placed N figurines on a straight shelf with integer coordinates from position 1 to position M.

The initial position of the i-th figurine (1 \leq i \leq N) is A_i. Multiple figurines may be at the same position. Also, figurines do not interfere with each other.

This initial arrangement is called state 0. Each state holds the information about the set of figurines remaining on the shelf and their respective positions.

We will create Q new states, numbered 1, 2, \ldots, Q, in order.

State j (j = 1, 2, \ldots, Q) is created by the following procedure:

1. Copy the contents of an already existing state P_j (0 \leq P_j \leq j-1) (the figurines remaining on the shelf and their positions) to use as the initial contents of the new state j.
2. Perform the following operation exactly once on state j:

• If C_j is L: Decrease the position of every figurine on the shelf in state j by D_j (slide them D_j to the left).
• If C_j is R: Increase the position of every figurine on the shelf in state j by D_j (slide them D_j to the right).
• As a result, any figurine whose position becomes less than 1 or greater than M falls off the shelf and is removed from state j.

Creating a new state by copying does not change the source state in any way.

Note that due to the way the source state number P_j is chosen, a tree structure rooted at state 0 is formed.

For each j = 1, 2, \ldots, Q, determine the number of figurines that have fallen off the shelf in state j (that is, the value of N minus the number of figurines remaining in state j).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq M (1 \leq i \leq N)
• 0 \leq P_j \leq j - 1 (1 \leq j \leq Q)
• C_j is L or R (1 \leq j \leq Q)
• 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
• All inputs are integers (except for C_j)

Sample Input 1

5 10 4
1 3 5 8 10
0 R 2
0 L 1
1 L 4
2 R 10

Sample Output 1

1
1
2
5

Sample Input 2

6 7 6
2 2 4 6 7 7
0 L 1
0 R 1
1 R 3
2 L 5
3 L 2
5 R 10

Sample Output 2

0
2
3
5
3
6

Sample Input 3

15 100 12
1 5 10 20 20 35 50 65 70 80 90 95 100 42 58
0 R 10
0 L 15
1 R 40
1 L 5
2 R 60
2 L 10
3 L 30
4 R 25
5 R 1
6 L 1
8 L 70
10 R 90

Sample Output 3

2
3
7
2
10
5
7
4
10
5
10
14

Sample Input 4

30 1000000000 25
1 2 3 100 1000 100000 123456789 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 999999999 1000000000 42 4242 424242 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998
0 R 1
0 L 1
1 R 999999998
1 L 50
2 R 123456789
2 L 999999999
3 L 500000000
3 R 2
4 R 1000
4 L 1000
5 R 700000000
5 L 200000000
6 R 1
7 L 1
8 R 400000000
9 L 400000000
10 R 600000000
11 L 600000000
12 R 333333333
13 L 333333333
14 R 999999999
15 L 999999999
16 R 123
20 L 456
24 R 789

Sample Output 4

1
1
29
5
7
30
29
30
7
7
20
15
30
29
30
18
20
20
17
30
30
30
18
30
30

Sample Input 5

1 1 1
1
0 R 1000000000

Sample Output 5

1

Problem Statement

Takahashi is trying to create a playlist from 2N candidate songs.

The i-th song (1 \leq i \leq 2N) belongs to genre B_i and has a duration of A_i seconds.

Takahashi selects one or more songs from the candidates (each song can be selected at most once) and arranges them in any order he likes to create a playlist.

However, the total duration of the selected songs must be at least K seconds.

In the created playlist, the maximum number of songs contained in a consecutive segment where all songs belong to the same genre is called the "bias score."

More precisely, consider all consecutive subsequences of songs in the playlist such that all songs in each subsequence belong to the same genre; the bias score is the maximum number of songs among all such subsequences.

Among all possible ways to select and arrange songs that satisfy the conditions, find the minimum possible bias score.

If the total duration is less than K seconds even when all songs are selected, and thus the condition cannot be satisfied, output -1.

Constraints

• 1 \leq N \leq 150
• 1 \leq K \leq 10^9
• 1 \leq B_i \leq 2N
• 1 \leq A_i \leq 10^6
• All input values are integers

Sample Input 1

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

Sample Output 1

1

Sample Input 2

2 31
1 8
2 7
2 6
3 9

Sample Output 2

-1

Sample Input 3

8 120
1 15
1 12
2 20
2 7
3 9
3 18
4 25
5 5
5 14
6 11
7 30
7 6
8 10
9 16
10 8
10 13

Sample Output 3

1

Sample Input 4

20 650
1 45
1 32
1 28
2 60
2 15
3 22
3 48
4 35
4 40
5 10
5 55
6 70
6 18
7 25
7 27
8 80
9 12
9 44
10 33
10 36
11 90
12 14
12 29
13 50
13 52
14 20
15 65
15 17
16 31
16 39
17 75
18 11
18 24
19 46
20 58
21 13
22 41
23 30
24 62
25 19

Sample Output 4

1

Sample Input 5

1 2
1 1
1 1

Sample Output 5

2