Problem Statement

Takahashi is creating punched cards as teaching materials for his information class.

A punched card is arranged in an N \times M grid, where each cell either has a hole punched in it or not. We will draw a diagram using . for cells with holes and # for cells without holes.

Takahashi initially prepared a card with no holes in any cell (all cells are #). After that, following Aoki's instructions, he decided to punch holes in K locations.

The positions of the holes specified by Aoki are represented by coordinates (R_i, C_i) (1 \leq i \leq K). Here, (R_i, C_i) refers to the cell in the R_i-th row from the top and the C_i-th column from the left.

Output the state of the card after punching holes according to Aoki's instructions.

Constraints

• 1 \leq N \leq 1000
• 1 \leq M \leq 1000
• 1 \leq K \leq N \times M
• 1 \leq R_i \leq N (1 \leq i \leq K)
• 1 \leq C_i \leq M (1 \leq i \leq K)
• (R_i, C_i) \neq (R_j, C_j) (i \neq j)
• All inputs are integers

Sample Input 1

3 4 2
1 2
2 3

Sample Output 1

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

Sample Input 2

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

Sample Output 2

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

Sample Input 3

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

Sample Output 3

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

Problem Statement

Takahashi has a sequence of N integers. The i-th element of the sequence is A_i.

Takahashi wants to count the number of pairs where he selects two different elements from this sequence such that their difference is exactly K.

Among all ways to select 2 elements from the N elements, find the number of pairs where the absolute difference of the two selected elements is exactly K. Note that a pair of the i-th element and the j-th element is counted as the same pair as the j-th element and the i-th element.

Constraints

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

Sample Input 1

5 2
1 3 5 7 9

Sample Output 1

4

Sample Input 2

7 3
1 4 7 10 2 5 8

Sample Output 2

5

Sample Input 3

10 100
50 150 250 350 450 200 300 400 500 600

Sample Output 3

8

Problem Statement

Takahashi's house has N light bulbs, numbered from 1 to N. Initially, all light bulbs are off.

Takahashi has a switch panel. This panel has M switches, numbered from 1 to M. The j-th switch affects c_j light bulbs. Specifically, pressing the j-th switch toggles the states of light bulbs s_{j,1}, s_{j,2}, \ldots, s_{j,c_j} (lit bulbs turn off, and unlit bulbs turn on).

For each of the M switches, Takahashi independently chooses whether to press it or not. Each switch can be pressed at most once.

Takahashi wants the number of lit light bulbs after all switch operations are completed to be exactly K. Determine whether this is achievable, and if so, find the minimum number of switches that need to be pressed.

Constraints

• 1 \leq N \leq 23
• 1 \leq M \leq 23
• 0 \leq K \leq N
• 1 \leq c_j \leq N (1 \leq j \leq M)
• 1 \leq s_{j,k} \leq N (1 \leq j \leq M,\ 1 \leq k \leq c_j)
• s_{j,1}, s_{j,2}, \ldots, s_{j,c_j} are all distinct (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 3 2
2 1 2
2 2 3
1 1

Sample Output 1

1

Sample Input 2

2 2 1
2 1 2
2 1 2

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

1

Sample Input 4

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

Sample Output 4

1

Sample Input 5

1 1 0
1 1

Sample Output 5

0

Problem Statement

Takahashi and Aoki are engaged in a battle over the territory of a kingdom.

The kingdom consists of N cities, numbered 1 to N. The cities are connected by roads, forming a rooted tree structure as a whole. City 1 is the capital and serves as the root of the tree. For each city i (2 \leq i \leq N), its parent city is City P_i. Each city i (1 \leq i \leq N) has an integer V_i representing its resource value. The resource value can be negative, which means occupying it will result in a loss.

The battle consists of two phases: "Road Blockade" and "Occupation Game".

Phase 1: Road Blockade

Before the occupation game begins, Aoki is given a special authority. After looking at the tree structure and all resource values of the cities, Aoki can choose to block exactly one edge (road) in the tree, or block no edges at all. However, if there are no edges in the tree (i.e., when N = 1), he must choose not to block any.

If a road is blocked, the tree is split into two connected components. At this point, only the connected component containing the capital (City 1) will be used for the occupation game, and the cities and roads in the other connected component are removed from the game. The root of the tree used for the game remains City 1, and the parent-child relationships among the remaining cities are inherited directly from the original tree. If no road is blocked, the entire original tree is used for the game.

Phase 2: Occupation Game

After the road blockade phase, all cities in the game start in an unoccupied state. The two players take turns, with Takahashi going first.

A city is said to be occupiable if it satisfies both of the following conditions:

• The city is currently unoccupied.
• The city is the capital (City 1), or its parent city is already occupied.

Here, "occupied" means the city has been occupied by either Takahashi or Aoki in a previous turn. In determining whether a city is occupiable, it does not matter whether Takahashi or Aoki occupied its parent. Since the capital has no parent, it is always occupiable as long as it is unoccupied.

On a player's turn, if there is at least one occupiable city, the player must choose and occupy exactly one of them (passing is not allowed). The game ends immediately when there are no more occupiable cities.

Objective

Let S be the set of all occupied cities at the end of the game.

Takahashi wants to maximize the total resource value \displaystyle\sum_{i \in S} V_i, and Aoki wants to minimize this same value.

Aoki will optimally perform the road blockade in Phase 1 and play optimally in the Phase 2 occupation game. Takahashi will also play optimally in Phase 2.

Find the value of \displaystyle\sum_{i \in S} V_i at the end of the game when both players make all their choices optimally.

Constraints

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

Sample Input 1

3
5 -2 4
1 1

Sample Output 1

3

Sample Input 2

5
3 8 -5 2 -10
1 2 2 3

Sample Output 2

-4

Sample Input 3

12
10 -4 7 3 -8 6 -2 5 -1 9 -6 4
1 1 2 2 3 3 4 6 6 7 10

Sample Output 3

5

Sample Input 4

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

Sample Output 4

12

Sample Input 5

1
-1000000000

Sample Output 5

-1000000000

Problem Statement

Takahashi found N sweets at a candy store. These sweets are numbered 1 to N, and the satisfaction level of the i-th sweet is A_i.

Takahashi is considering choosing and buying K distinct sweets out of the N sweets. Find the number of ways to choose K sweets such that the total satisfaction level of the chosen sweets is at least X.

Two ways of choosing sweets are considered different if the set of chosen sweets' numbers (indices) is different.

Constraints

• 1 \leq N \leq 36
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq K \times 10^9
• All input values are integers.

Sample Input 1

4 2 7
2 4 5 7

Sample Output 1

5

Sample Input 2

5 3 20
1 2 3 4 5

Sample Output 2

0

Sample Input 3

16 7 100
3 8 12 17 5 21 9 14 6 25 11 19 4 16 23 7

Sample Output 3

2291

Sample Input 4

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

Sample Output 4

4594114161

Sample Input 5

1 1 1
1

Sample Output 5

1