Problem Statement

Takahashi is playing a card game.

N cards are arranged in a row on the table. The i-th card from the left is called "card i", and card i has an attack power of A_i written on it.

Takahashi performs the following operation exactly once for each i, in the order i = 1, 2, \ldots, N-1. Note that the operation targets the pair of cards with numbers i and i+1, not cards that are physically adjacent on the table. A card's number does not change even after it is removed from the table.

• If at least one of card i and card i+1 has already been removed from the table, do nothing.
• If both card i and card i+1 remain on the table, compare their current attack powers.
• If their attack powers are equal, do nothing.
• If their attack powers differ, the card with the higher attack power absorbs the other. Specifically, when a card with attack power X absorbs a card with attack power Y (X > Y), the following occurs:
• The absorbed card (with attack power Y) is removed from the table and is treated as no longer on the table in subsequent operations.
• The absorbing card remains on the table with the same number, and its attack power is updated to X + \lfloor Y / 2 \rfloor, where \lfloor \cdot \rfloor denotes the floor function (rounding down to the nearest integer). This updated attack power is used in subsequent operations.

Note that since a card's attack power can change through absorption, the latest attack power at the time of each operation is used for comparison.

After all operations up to i = N-1 have been completed, find the number of cards remaining on the table.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

3

Sample Input 2

4
2 2 2 2

Sample Output 2

4

Sample Input 3

10
5 3 8 6 2 7 1 9 4 10

Sample Output 3

5

Sample Input 4

20
100 37 85 12 99 44 67 23 78 56 91 33 72 15 88 41 63 29 50 1000000000

Sample Output 4

10

Sample Input 5

1
1

Sample Output 5

1

Problem Statement

Takahashi has been assigned the task of determining this year's scholarship recipients as a member of the university's scholarship selection committee.

This year, N students have applied for the scholarship, and each student is assigned a number from 1 to N. The selection evaluates grades (scores) in M subjects, where student i's score in subject j is S_{i,j} points.

Additionally, each subject j has a minimum threshold score T_j. The scholarship recipients are determined by the following procedure.

Step 1: Determining Qualifying Students

Student i is called a "qualifying student" if they satisfy S_{i,j} \geq T_j for all subjects j (1 \leq j \leq M).

Step 2: Determining Recipients

Recipients are determined based on the number of qualifying students as follows. Here, K is a positive integer given as the selection quota.

• If the number of qualifying students is K or fewer, all qualifying students become recipients. In particular, if there are 0 qualifying students, then there are 0 recipients.
• If the number of qualifying students is more than K, recipients are selected as follows. For each qualifying student i, compute the total score across all subjects \displaystyle P_i = \sum_{j=1}^{M} S_{i,j}. Sort the P_i values of all qualifying students in descending order, and let the K-th value from the top be the borderline B (since there are more than K qualifying students, the K-th value always exists). All qualifying students with P_i \geq B become recipients.

> Note: If multiple qualifying students have the same total score as the borderline B, the number of recipients may exceed K.

On behalf of Takahashi, determine the student numbers of the recipients.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10
• 1 \leq K \leq N
• 0 \leq T_j \leq 1000 (1 \leq j \leq M)
• 0 \leq S_{i,j} \leq 1000 (1 \leq i \leq N, 1 \leq j \leq M)
• All input values are integers.

Sample Input 1

5 3 2
50 60 55
80 70 60
40 80 70
90 65 80
55 60 55
70 75 90

Sample Output 1

3
5

Sample Input 2

8 2 3
30 30
50 50
80 90
40 60
70 80
20 90
60 90
90 80
35 65

Sample Output 2

2
4
6
7

Sample Input 3

10 4 5
70 65 60 75
80 70 65 80
50 90 80 70
75 68 62 90
60 65 70 80
90 80 75 85
72 66 61 76
30 40 50 60
85 70 60 80
70 65 60 74
95 85 80 90

Sample Output 3

1
3
5
8
10

Problem Statement

Takahashi manages an orchard and has planted N fruit trees in a row. Each tree is numbered from 1 to N, and tree i bears A_i fruits.

The trees in this orchard have a mysterious property: no matter how many times they are harvested, the number of fruits on them does not decrease.

The harvest points P_i of each tree are initially 0. When a tree is harvested once, the number of fruits on that tree is added to its harvest points. For example, if a tree bearing 5 fruits is harvested 3 times, its harvest points become 5 \times 3 = 15.

The harvest season has arrived, and Takahashi will carry out harvesting over M days.

• On day j, he harvests once from every tree numbered from L_j to R_j (trees L_j, L_j + 1, \ldots, R_j).

After all harvesting is complete, determine the harvest points P_1, P_2, \ldots, P_N of each tree.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq L_j \leq R_j \leq N
• All inputs are integers
• The answers fit within the range of a 64-bit signed integer

Sample Input 1

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

Sample Output 1

3 2 12 2 5

Sample Input 2

7 5
10 20 30 40 50 60 70
1 7
2 5
3 3
1 4
5 7

Sample Output 2

20 60 120 120 150 120 140

Sample Input 3

10 8
100 200 300 400 500 600 700 800 900 1000
1 5
3 8
6 10
2 4
1 10
5 5
7 9
1 3

Sample Output 3

300 800 1500 1600 2000 1800 2800 3200 2700 2000

Problem Statement

Takahashi is trying to eat vegetables and fruits in a balanced way every day for his health. After summarizing his meal records over N days, he obtained a string S of length N. The i-th character of S represents the meal content on day i, and is one of the following:

• V : Ate only vegetables
• F : Ate only fruits
• B : Ate both vegetables and fruits
• N : Ate neither

The vegetable score v_i and fruit score f_i for day i are defined according to the meal content as follows:

For a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, if the total vegetable score \displaystyle\sum_{i=l}^{r} v_i and the total fruit score \displaystyle\sum_{i=l}^{r} f_i over the interval from day l to day r are equal, then that interval is called a balanced period. This includes the case where both totals are 0.

Find the number of pairs (l, r) that form a balanced period.

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N, and each character is one of V, F, B, N

Sample Input 1

5
VFBNN

Sample Output 1

10

Sample Input 2

4
BNNF

Sample Output 2

6

Sample Input 3

12
VFBNVFBNVFBN

Sample Output 3

48

Sample Input 4

32
VVFFBBNNVVFFBBNNVVFFBBNNVVFFBBNN

Sample Output 4

244

Sample Input 5

1
N

Sample Output 5

1

Problem Statement

In Takahashi's company, the management structure of employees is represented by an organizational chart in the form of a tree structure.

Employees are numbered from 1 to N. Employee 1 is the president and is positioned at the top (root) of the organizational chart.

Each employee i (2 \le i \le N) has exactly one direct superior, whose number is P_i.

This information defines a rooted tree with N vertices, rooted at employee 1.

If employee b can be reached from employee a by following direct superiors zero or more times, then employee b is called a superior of employee a.

In particular, each employee is also a superior of themselves. Additionally, employee 1 is a superior of all employees.

In a rooted tree, the depth of a vertex is the number of edges on the path from the root to that vertex. The depth of the root (employee 1) is 0.

You are given Q queries.

In the k-th query, employee numbers X_k and Y_k are given. Find the employee number of the employee who is a superior of both employee X_k and employee Y_k and has the greatest depth. It can be proven that exactly one such employee exists.

Note that if employee X_k is a superior of employee Y_k, the answer is X_k, and if employee Y_k is a superior of employee X_k, the answer is Y_k (including the case where X_k = Y_k).

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 5 \times 10^4
• 1 \leq P_i < i (2 \leq i \leq N)
• 1 \leq X_k, Y_k \leq N (1 \leq k \leq Q)
• All input values are integers

Sample Input 1

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

Sample Output 1

2
1
3
1
3

Sample Input 2

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

Sample Output 2

1
1
5
1
1

Sample Input 3

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

Sample Output 3

4
2
6
10
1
10
1
3

Sample Input 4

25 14
1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 10 11 13 14 16 18 21
20 12
20 25
22 23
24 19
17 23
14 15
21 6
18 24
1 25
11 12
5 6
8 16
17 18
2 25

Sample Output 4

5
2
3
10
1
7
6
18
1
5
2
8
4
2

Sample Input 5

2 4
1
1 1
1 2
2 2
2 1

Sample Output 5

1
1
2
1