If you visit the prehistoric stone circle of Stonehenge at dawn on the longest day of the year, the druids will challenge you to participate in the ancient and sacred pebble game. First, you will be blindfolded, so that you are unable to see anything.

Then, the chief druid will tell you that she has $$$N$$$ piles of stones in a line, where $$$N$$$ is a power of two ($$$N = 2^k$$$ for some integer $$$k$$$).

Piles are indexed from $$$0$$$ to $$$N-1$$$. Each pile has a height $$$H_i$$$, which is a positive integer, and the piles are ordered from smallest to tallest ($$$H_0 \le H_1 \le \ldots \le H_{N-1}$$$). The chief druid tells you the value of $$$N$$$, but not the initial heights.

You can then choose actions of one of the following types:

1. Select a positive number $$$X$$$ and a subset of the piles $$$S$$$. The druids will then add $$$X$$$ stones to each of the piles in $$$S$$$, and then reorder the piles from smallest to largest.
2. Choose two piles $$$i$$$ and $$$j$$$. The druids will then tell you whether these two piles currently have the same height.

Your goal is to reach a configuration where all piles have the same height. You take at most $$$Q_\mathrm{add}$$$ actions of the first type, and at most $$$Q_\mathrm{compare}$$$ actions of the second type (see section Scoring).

Implementation Details

You will have to submit a single .cpp source file.

Among this task's attachments you will find a template equal.cpp with a sample implementation.

You have to implement the following function:

void make_all_equal(int N, int Q_add, int Q_compare);

• Integer $$$N$$$ represents the number of piles.
• Integer $$$Q_\mathrm{add}$$$ represents the maximum number of times you can call add.
• Integer $$$Q_\mathrm{compare}$$$ represents the maximum number of times you can call compare.

You can call the following functions:

void add(vector<int> S, long long X);

• The vector $$$S$$$ must contain distinct integers between $$$0$$$ and $$$N-1$$$ inclusive.
• Integer $$$X$$$ must be between $$$0$$$ and $$$10^{12}$$$ inclusive.
• This function will increment $$$H_i$$$ by $$$X$$$ for every $$$i$$$ in $$$S$$$. Then, it will sort the heights in increasing order ($$$H_0 \le \ldots \le H_{N-1}$$$).
• This function can be called at most $$$Q_\mathrm{add}$$$ times.

bool compare(int i, int j);

• $$$i$$$ and $$$j$$$ must be between $$$0$$$ and $$$N-1$$$ inclusive.
• The function will return true if the $$$i$$$-th smallest pile and the $$$j$$$-th smallest pile have the same current height (that is, if $$$H_i = H_j$$$), and false otherwise.
• This function can be called at most $$$Q_\mathrm{compare}$$$ times.

Hampton Court Palace (in Richmond, just southwest of London) is famous for its maze, which was planted by King William III in the 1690s. Since the palace is now open to the public as a tourist attraction, the royal authorities have decided to replace the maze with an updated version. They have estimated the number of tourists $$$K$$$ they expect to visit during the season, and they would like the new maze to have exactly $$$K$$$ possible routes through it, allowing each visitor to have a unique experience.

The maze is a grid of $$$N$$$ rows and $$$M$$$ columns, where each cell can be either empty or contain a hedge. The maze is surrounded by a fence, and there is a single entrance and a single exit. The entrance is in the top-left cell, and the exit is in the bottom-right cell. The visitor must complete the maze by making only right and down moves. Due to space constraints, the maze can have no more than 200 rows and no more than 200 columns.

Your task is to design a maze with exactly $$$K$$$ routes from the entrance to the exit involving only right and down moves.

Implementation Details

You will have to submit a single .cpp source file. Among this task's attachments you will find a template mazes.cpp with a sample implementation.

You have to implement the following function:

vector<vector<char>> solve(long long K);

• Integer $$$K$$$ represents the desired number of routes through the maze.
• The function should return a two dimensional vector of characters, representing the maze.
• The returned maze should have $$$N$$$ rows and $$$M$$$ columns, for some $$$N, M \le 200$$$.
• Each cell of the maze should be either a . (dot) for an empty cell or a # (hash) for a cell containing a hedge.
• The entrance is in the cell $$$(0, 0)$$$ and the exit is in the cell $$$(N - 1, M - 1)$$$.
• The maze should have exactly $$$K$$$ different ways to go through it from the entrance to the exit by making only right and down moves.

The grader will call the function solve and will print its return value to the output file.

Your program will be tested on a set of test cases grouped by subtask. To obtain the score associated to a subtask, you need to correctly solve all the test cases it contains.

• Subtask 1 [0 points] Sample test cases
• Subtask 2 [9 points] $$$K \le 10$$$.
• Subtask 3 [25 points] $$$K \le 99$$$.
• Subtask 4 [27 points] $$$K$$$ is a power of two.
• Subtask 5 [39 points] No additional constraints.

In order to deliver parcels more efficiently, the Post Office has constructed a network of pneumatic tubes beneath the streets of London. The network consists of $$$N$$$ routing stations connected by $$$N-1$$$ undirected tubes. There is a unique path between any pair of stations, and parcels will be sent along the path from their source to their destination.

When a parcel is at routing station $$$i$$$, there are two options for sending it on towards its destination. It can be fired at low power at a cost of $$$A_i$$$, in which case it will travel along a single tube to the next station along its route. Alternatively, it can be fired at high power. In this case, the operator will select a dial setting $$$k\geq 1$$$, and the parcel will travel along the next $$$k$$$ tubes of its route, at a cost of $$$B_i + k\cdot C$$$.

The Post Office will route parcels so as to minimise total cost, but in order to avoid congestion on the network parcels must stay on the direct route from their source to their destination. Your task is to find the minimum costs for a series of $$$Q$$$ parcels to be sent in this network.

Implementation Details

You will have to submit a single .cpp source file.

Among this task's attachments you will find a template multihop.cpp with a sample implementation.

You have to implement the following functions:

void init(int N, int C, vector<int> A, vector<int> B, vector<int> U, vector<int> V);
long long query(int X, int Y);

• Integer $$$N$$$ represents the number of routing stations.
• Integer $$$C$$$ represents the incremental cost per unit of power when firing at high power, as described above.
• The array $$$A$$$, indexed from $$$0$$$ to $$$N - 1$$$, contains the cost of firing at low power from each node.
• The array $$$B$$$, indexed from $$$0$$$ to $$$N - 1$$$, contains the basic cost of firing at high power from each node, as described above.
• The arrays $$$\mathit{U}$$$ and $$$\mathit{V}$$$ describe the tubes in the network: there is a tube between routing station $$$\mathit{U}[i]$$$ to routing station $$$\mathit{V}[i]$$$.
• query should return the minimum cost of sending a parcel from routing station $$$X$$$ to routing station $$$Y$$$.

The grader will call the function init, and then will call query $$$Q$$$ times, printing its return value to the output file.

Your program will be tested on a set of test cases grouped by subtask. To obtain the score associated to a subtask, you need to correctly solve all the test cases it contains.

• Subtask 1 [0 points] Sample test cases.
• Subtask 2 [6 points] $$$A_i \le 10$$$, $$$B_i \le 10$$$ for each $$$i = 0, \, \dots, \, N - 1$$$, $$$C \le 10$$$, $$$N \le 10$$$, $$$Q \le 10$$$.
• Subtask 3 [10 points] $$$N \le 5000$$$, $$$Q = 1$$$.
• Subtask 4 [22 points] $$$N \le 10^5$$$, $$$Q = 1$$$.
• Subtask 5 [28 points] $$$N \le 5000$$$.
• Subtask 6 [34 points] No additional constraints.

The British spy agency MI6 is planning to infiltrate a network of double agents into the sinister criminal organisation SPECTRE. SPECTRE has $$$N$$$ employees, numbered from $$$0$$$ to $$$N-1$$$, and their organisation chart is a tree on these $$$N$$$ vertices.

MI6 will select a non-empty set $$$S$$$ of SPECTRE employees to turn into double agents. Because of the risk of further treachery (i.e. possible triple-agents), it is essential that the chain of communication between any two double-agents passes only through 'innocent' employees. That is, for any two distinct employees $$$a$$$ and $$$b$$$ in $$$S$$$, the simple path between $$$a$$$ and $$$b$$$ in the tree must not contain any other employees in $$$S$$$.

Your task is to count the number of possible sets $$$S$$$ of double agents. Since this value can be quite large, output the value modulo $$$10^9 + 7$$$.

Implementation Details

You will have to submit a single .cpp source file.

Among this task's attachments you will find a template trees.cpp with a sample implementation.

You have to implement the following function:

int count_sets(int N, vector<int> U, vector<int> V);

• Integer $$$N$$$ represents the number of employees of SPECTRE.
• The arrays $$$U$$$ and $$$V$$$, indexed from $$$0$$$ to $$$N - 2$$$, contains the values $$$U_0, \, U_1, \, \dots, \, U_{N - 2}$$$ and $$$V_0, \, V_1, \, \dots, \, V_{N - 2}$$$, where $$$U_i$$$ and $$$V_i$$$ are the endpoints of the $$$i$$$-th edge in the organisation tree.
• The function should return the number of possible sets modulo $$$10^9 + 7$$$.

The grader will call the function count and will print its return value to the output file.

Your program will be tested on a set of test cases grouped by subtask. To obtain the score associated to a subtask, you need to correctly solve all the test cases it contains.

[nolistsep, itemsep=2mm]
• Subtask 1 [0 points] Sample test cases.
• Subtask 2 [13 points] $$$N \le 16$$$.
• Subtask 3 [15 points] The tree is a path. A path is a tree where the nodes can be arranged in some order $$$P_0, P_1, \ldots, P_{N - 1}$$$ in which there exists an edge between nodes $$$P_i$$$ and $$$P_{i + 1}$$$ for all $$$0 \le i \le N - 2$$$.
• Subtask 4 [14 points] $$$N \le 500$$$, and the tree is a caterpillar. A caterpillar is a path with some additional leaf nodes attached. That is, the vertices of the tree can be written as $$$P_0,\ldots, P_k, Q_0,\ldots, Q_l$$$, where $$$P_0,\ldots,P_k$$$ is a path and each $$$Q_i$$$ is a leaf (i.e. has degree 1).
• Subtask 5 [15 points] $$$N \le 5000$$$, and the tree is a caterpillar.
• Subtask 6 [14 points] $$$N \le 5 \times 10^5$$$, and the tree is a caterpillar.
• Subtask 7 [29 points] No additional constraints.