Problem Statement

Takahashi is taking a walk along a road with N points arranged in a straight line. The points are numbered 1, 2, \ldots, N from left to right, and points whose numbers differ by 1 are adjacent to each other.

Along this road, M cherry blossom trees are planted. The i-th cherry blossom tree is planted at point P_i, and when Takahashi visits that point, V_i petals fall down, all of which Takahashi receives. At most one cherry blossom tree is planted at each point.

Takahashi starts at point S and moves to point T. He proceeds one adjacent point at a time from S toward T, without ever turning back. Therefore, the points Takahashi visits, including the start and goal points, are as follows:

• When S \leq T: S, S+1, \ldots, T
• When S > T: S, S-1, \ldots, T

If S = T, Takahashi does not move and only visits point S.

Since Takahashi moves in only one direction, he visits each point exactly once. Find the total number of petals Takahashi receives while moving from point S to point T.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S \leq N
• 1 \leq T \leq N
• 1 \leq P_i \leq N (1 \leq i \leq M)
• 1 \leq V_i \leq 10^9 (1 \leq i \leq M)
• P_i \neq P_j (i \neq j)
• All input values are integers

Sample Input 1

10 5
3 8
1 10
3 5
5 7
8 2
10 100

Sample Output 1

14

Sample Input 2

100 12
40 15
5 12
10 7
15 100
18 30
20 8
25 50
30 3
35 20
40 200
41 9
60 15
90 1

Sample Output 2

411

Sample Input 3

1000000000 25
999999920 999999970
1 111
2 222
100000000 333
123456789 444
400000000 555
500000000 666
700000000 777
800000100 888
999999999 999
999999910 4
999999919 70
999999920 100
999999923 1
999999930 500000000
999999934 20
999999940 300
999999945 999999999
999999950 42
999999955 17
999999960 250000000
999999966 6
999999970 8
999999971 90
999999972 3
999999980 5

Sample Output 3

1750000493

Problem Statement

Takahashi is going to create mosaic art for the school festival.

First, Takahashi prepared a design draft in the form of a grid with H rows and W columns. Each cell of the grid is either # (filled) or . (blank).

Based on this design draft, Takahashi creates the mosaic art using the following procedure.

Step 1: Enlargement

Enlarge the design draft by a factor of K both vertically and horizontally. Specifically, replace each cell of the draft with a block of K rows and K columns filled with the same character, obtaining a grid of (H \times K) rows and (W \times K) columns consisting of # and ..

Step 2: Character Assignment

In the (H \times K) by (W \times K) grid obtained in Step 1, replace all # with character c_1 and all . with character c_2. Here, c_1 and c_2 are each a single character that is either a lowercase English letter (a–z) or an uppercase English letter (A–Z). It is possible that c_1 and c_2 are the same character.

Output the resulting mosaic art of (H \times K) rows and (W \times K) columns.

Constraints

• 1 \leq H \leq 100
• 1 \leq W \leq 100
• 1 \leq K \leq 50
• H, W, K are all integers
• c_1 is a single character that is either a lowercase English letter (a–z) or an uppercase English letter (A–Z)
• c_2 is a single character that is either a lowercase English letter (a–z) or an uppercase English letter (A–Z)
• c_1 and c_2 may be the same character
• S_i is a string of length W consisting of # and .

Sample Input 1

3 3 2
X o
#.#
.#.
#.#

Sample Output 1

XXooXX
XXooXX
ooXXoo
ooXXoo
XXooXX
XXooXX

Sample Input 2

2 4 3
A B
#..#
.##.

Sample Output 2

AAABBBBBBAAA
AAABBBBBBAAA
AAABBBBBBAAA
BBBAAAAAABBB
BBBAAAAAABBB
BBBAAAAAABBB

Sample Input 3

5 6 4
R w
#....#
.#..#.
..##..
.#..#.
#....#

Sample Output 3

RRRRwwwwwwwwwwwwwwwwRRRR
RRRRwwwwwwwwwwwwwwwwRRRR
RRRRwwwwwwwwwwwwwwwwRRRR
RRRRwwwwwwwwwwwwwwwwRRRR
wwwwRRRRwwwwwwwwRRRRwwww
wwwwRRRRwwwwwwwwRRRRwwww
wwwwRRRRwwwwwwwwRRRRwwww
wwwwRRRRwwwwwwwwRRRRwwww
wwwwwwwwRRRRRRRRwwwwwwww
wwwwwwwwRRRRRRRRwwwwwwww
wwwwwwwwRRRRRRRRwwwwwwww
wwwwwwwwRRRRRRRRwwwwwwww
wwwwRRRRwwwwwwwwRRRRwwww
wwwwRRRRwwwwwwwwRRRRwwww
wwwwRRRRwwwwwwwwRRRRwwww
wwwwRRRRwwwwwwwwRRRRwwww
RRRRwwwwwwwwwwwwwwwwRRRR
RRRRwwwwwwwwwwwwwwwwRRRR
RRRRwwwwwwwwwwwwwwwwRRRR
RRRRwwwwwwwwwwwwwwwwRRRR

Problem Statement

Takahashi is in charge of forming teams for a programming contest. There are N candidates, numbered from 1 to N.

Each candidate i represents the set of skills they are proficient in as a bit representation of a non-negative integer A_i. Takahashi wants to select team members from these N people such that when the skills of all selected members are combined using bitwise OR, the team's overall skill set exactly matches the target value K.

Takahashi wants to include as many people as possible in the team.

Find the maximum number of candidates that can be selected from a non-empty subset of candidates such that the bitwise OR of all their skill values equals exactly K. If no such subset exists, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^{18}
• 0 \leq A_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5 7
3 5 6 1 9

Sample Output 1

4

Sample Input 2

4 3
4 8 16 32

Sample Output 2

-1

Sample Input 3

10 15
1 2 4 8 3 5 15 6 16 14

Sample Output 3

9

Problem Statement

Takahashi is investigating his family's genealogy. The family consists of N people, each numbered from 1 to N.

In this family tree, every person except person 1, who is the founding ancestor, has exactly one "parent." The parent of person i (2 \leq i \leq N) is person P_i. Through these parent-child relationships, all people form a rooted tree with person 1 as the root.

For each person i, the value V_i of the inheritance left by that person is recorded.

Takahashi defines the "cumulative inheritance" of a person X as the sum of the inheritance values of all people on the path from person X to the founding ancestor (person 1), obtained by repeatedly following the parent, including both person X themselves and person 1.

You are given Q queries. For each query, a person number X_j is specified. Find the cumulative inheritance of that person.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_i < i (2 \leq i \leq N)
• 1 \leq X_j \leq N (1 \leq j \leq Q)
• All input values are integers

Sample Input 1

5 3
10 20 30 40 50
1 1 2 2
1
4
5

Sample Output 1

10
70
80

Sample Input 2

7 5
100 200 300 150 250 50 400
1 1 2 2 3 3
1
3
5
6
7

Sample Output 2

100
400
550
450
800

Sample Input 3

10 8
1000000000 500000000 300000000 200000000 100000000 800000000 600000000 400000000 250000000 150000000
1 1 2 2 3 3 4 5 6
1
4
7
8
9
10
3
6

Sample Output 3

1000000000
1700000000
1900000000
2100000000
1850000000
2250000000
1300000000
2100000000

Problem Statement

Takahashi is an adventurer. After exploring a dungeon, he discovered N treasure chests.

The i-th treasure chest has a weight of A_i kilograms and a value of B_i.

Takahashi's backpack can hold treasure chests as long as their total weight is at most M kilograms. Takahashi plans to select some number of treasure chests (possibly zero) from the N chests to put in his backpack and carry home. However, since each treasure chest exists only once, the same chest cannot be selected multiple times.

Takahashi wants to maximize the total value of the selected treasure chests, subject to the constraint that the total weight of the selected chests is at most M kilograms. A selection that maximizes the total value is called an optimal selection. There may be multiple optimal selections.

For each treasure chest i (1 \leq i \leq N), determine whether there exists an optimal selection that includes treasure chest i.

Constraints

• 1 \leq N \leq 1,000
• 1 \leq M \leq 3,000
• 1 \leq A_i \leq M (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 5
2 3
3 4
3 3

Sample Output 1

Yes
Yes
No

Sample Input 2

4 4
2 5
2 5
2 5
3 1

Sample Output 2

Yes
Yes
Yes
No

Sample Input 3

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

Sample Output 3

Yes
Yes
Yes
No
Yes
No

Sample Input 4

10 15
3 10
4 12
5 14
2 7
1 3
6 18
7 20
8 22
3 9
4 11

Sample Output 4

Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No

Sample Input 5

1 1
1 1

Sample Output 5

Yes