Problem 1A. Archery Tournament ≡

Statement

You were invited to the annual archery tournament. You are going to compete against the best archers from all of the Northern Eurasia. This year, a new type of competition is introduced, where a shooting range is dynamic and new targets might appear at any second.

As the shooting range is far enough from you, it can be represented as a 2D plane, where y = 0 is the ground level. There are some targets in a shape of a circle, and all the targets are standing on the ground. That means, if a target's center is (x, y) (y > 0), then its radius is equal to y, so that it touches the line y = 0. No two targets simultaneously present at the range at any given time intersect (but they may touch).

Initially, the shooting range is empty. Your participation in this competition can be described as n events: either a new target appears at the range, or you shoot an arrow at some point at the range. To hit a target, you must shoot strictly inside the circle (hitting the border does not count). If you shoot and hit some target, then the target is removed from the range and you are awarded one point.

Input format

The first line of the input contains integer n (1 ≤ n ≤ 2 ⋅ 10⁵). Next n lines describe the events happening at the tournament. The i-th line contains three integers t_i, x_i, and y_i (t_i = 1, 2;  − 10⁹ ≤ x_i, y_i ≤ 10⁹; y_i > 0).

• If t_i = 1, then a new target with center (x_i, y_i) and radius y_i appears at the range.
• If t_i = 2, then you perform a shot, which hits the range at (x_i, y_i).

Output format

For each of your shots, output a separate line with the single integer. If the shot did not hit any target, print ``-1″. If the shot hit a target, print the number of event when that target was added to the range. Events are numbered starting from 1.

Sample tests

8
1 0 12
2 -11 22
1 24 10
1 12 3
2 12 12
2 16 14
1 28 15
2 3 6

-1
-1
3
1

Problem 1F. The Final Level ≡

Statement

Fiora is a game designer. Now she is designing the final level for her new game.

A level for this game is a labyrinth on a rectangular grid with lots of enemies. Player starts her game at the square (0, 0) and her purpose is to get to the square (a, b). Fiora has lots of ideas on how to put enemies, but she does not like designing labyrinths. She needs your help here.

Fiora is drawing levels in a special level editor which supports one basic block to design a labyrinth. This block is an L-shaped corner, consisting of two perpendicular rectangles 1 × n squares in size intersecting at 1 × 1 square.

It is possible to rotate this block in four ways. Blocks cannot intersect, but they can touch each other. Player can move through all the squares lying in any block. She can move between two squares if they are sharing a side, even if they are in different blocks.

Fiora wants to design the final level with the minimal possible number of blocks. Of course, it should be possible to move from square (0, 0) to square (a, b).

Input file format

The first line of the input consists of a single integer m (1 ≤ m ≤ 100) — the number of test cases.

It is followed by m test cases.

Each test case is on a separate line and consists of three integers a, b, and n ( − 10⁸ ≤ a, b ≤ 10⁸; 2 ≤ n ≤ 10⁸) — a is the coordinate of the final point along the horizontal axis, b is the coordinate of the final point along the vertical axis, and n is the size of the block.

The final point is not same as the starting one (either a ≠ 0 or b ≠ 0).

Output file format

For each test case, in the first line print the minimal number k of blocks you need. In the following k lines print description of these blocks.

Each L-shaped corner block is described by coordinates of two cells. Print coordinates of the end of its vertical rectangle, followed by coordinates of the end of its horizontal rectangle.

Specify the coordinates of the ends that are opposite to the intersection of the rectangles. Note that the order of cells in the block description matters, since a change of the order results in a reflected block. Coordinates of each end should be printed with the coordinate along the horizontal axis first, followed by the coordinate along the vertical axis.

All coordinates in the output should not exceed 10⁹ by absolute value.

It is guaranteed that the total number of blocks in the correct output does not exceed 10⁵ for all test cases combined.

Constraints

Sample tests

2
2 3 2
4 -1 3

2
1 1 0 0
1 2 2 3
2
0 0 2 -2
3 -3 5 -1

Problem 1L. Laminar Family ≡

Statement

While studying combinatorial optimization, Lucas came across the notion of «laminar set family». A subset family F of some set Ω is called laminar if and only if it does not contain an empty set and for any two distinct sets A, B ∈ F it is correct that either A ⊂ B or B ⊂ A or A ∩ B = varnothing.

As an experienced problem setter Lucas always tries to apply each new piece of knowledge he gets as an idea for a programming competition problem. An area of his scientific interests covers recognition problems that usually sound like «Given some weird combinatorial property, check if the given structure satisfies it».

Lucas believes that the perfect programming competition problem should contain a cactus a tree in it. Trying to put together laminar sets and trees into a recognition problem, he finally came up with the following problem: given an undirected tree on n vertices and a family F = {F₁, …, F_k} of sets, where F_i consists of all vertices belonging to the simple path between some two vertices a_i and b_i of the tree, check if the family F is a laminar family. Note that in this case Ω  = V, and each F_i ⊆ V.

As you can see, Lucas had succeeded in suggesting this problem to the programming contest. Now it is up to you to solve it.

Input file format

The first line of the input contains two integers n and f (1 ≤ n, f ≤ 100 000) — the number of vertices in the tree and the number of elements in a family F.

Next n − 1 lines describe the tree structure. In the i-th line there are two integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — the indices of the vertices that are connected by the i-th edge of the tree.

Next f lines describe the sets forming the family F. In the i-th line there are two integers a_i and b_i (1 ≤ a_i, b_i ≤ n), such that F_i consists of all vertices belonging to the simple path between vertices a_i and b_i in the tree (including a_i and b_i).

Output file format

Output the only word ``tYes″ or ``tNo″ depending on whether or not the given set family is laminar.

Constraints

Sample tests

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

No

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

Yes

Problem 2E. Expect to Wait ≡

Statement

Mayor Adam East wants to improve the public transport network of Harshel city by introducing the network of stations with unicycles. Any person who owns a special card can come to a station and request a unicycle to ride or drop one.

The procedure of requesting a unicycle is simple. The person enters a queue. If there is a unicycle available, then the first person from the queue takes it immediately. Otherwise, people in the queue wait until someone drops a unicycle at the station.

Let the wait time be the time that person spends between the request (entrance to the queue) and obtaining a unicycle. If the person does not receive a unicycle at all, then the wait time is infinity. The total wait time is the sum of wait times for each person.

Adam already knows the schedule of all the people for every day. He knows at what times people request and drop unicycles at the Central Station that can hold any number of unicycles at the same time. The only thing he does not know is how many unicycles should be placed there at the start of each day. He asks you several questions to calculate the total wait time given the starting number of unicycles.

Input file format

The first line contains n and q (1 ≤ n, q ≤ 10⁵), where n is the total number of unicycle requests and unicycle drops at the Central Station, and q is the number of questions Adam asks you.

The next n lines describe operations at the Central Station. Each line contains one description of operation:

• «+ t k» when k unicycles are dropped at time t;
• «- t k» when k people request unicycles at time t.

For each of the described operations 1 ≤ t ≤ 10⁹ and 1 ≤ k ≤ 10⁴.

The last line of the input contains q different integers b_i (0 ≤ b_i ≤ 10⁹) — the number of unicycles at the start of the day.

The operations are given in the strongly increasing order of time.

Output file format

The output shall consist of q lines. The i-th line shall display the total wait time for the case of b_i unicycles at the start of the day. If the total wait time is infinite, then the corresponding line shall display the word «INFINITY».

Constraints

Sample tests

5 4
- 1 1
- 2 2
+ 4 1
- 6 1
+ 7 2
0 3 1 2

INFINITY
0
8
3

Problem 2F. Foreign Postcards ≡

Statement

Fedor is an avid traveler. As a result of his hobby, he has gathered a big collection of postcards from all over the world. Each postcard has a unique picture on the front side and some fields for address information and text on the back side.

During one of the parties at Fedor's house, he decided to show all his of postcards to the guests. To achieve that, he wants to lay them all out on the table. Initially, all of his postcards are arranged in a single stack that Fedor is holding in his hands. Unfortunately, some of the postcards in that stack can be turned incorrectly — upside down. Ideally, Fedor would like all postcards on the table to lie with the picture on top, but looking at every postcard and turning it over individually can be very time-consuming. Instead, he came up with the following process:

1. Let n be the number of postcards remaining in the stack in his hands. Fedor chooses a random number k uniformly between 1 and n and takes top k postcards from the stack.
2. He looks at the topmost postcard among these k postcards. If it is oriented in the wrong way, he turns the whole stack of k postcards upside down together.
3. He then puts these k postcards on the table without any further rotations.
4. If there are still some postcards remaining in the stack in his hands, Fedor goes back to step 1.

Of course, after all the postcards are on the table, there might still be some that lie back side up. What is the expected number of such postcards?

Input file format

The input consists of a single line of «C» and «W» characters — i-th character corresponds to i-th postcard in the stack, counting from the top of the stack. «C» means that i-th postcard is oriented correctly in the initial stack, and «W» means that i-th postcard is oriented in the wrong way. The number of characters is between 1 and 10⁶ inclusive.

Output file format

Output one real number — the expected number of incorrectly placed postcards on the table. The absolute or relative error should not exceed 10^− 9.

Constraints

Sample tests

CWCC

1.0

WWCWCCW

2.333333333333

Problem 2J. Jenga Boom ≡

Statement

Jane is a game designer and she designs the next version of Jenga Boom, where the blocks have dimensions of 1 × w × wn instead of the ordinary 1 × 2 × 6.

As usual, the initial tower is created at the game start. It consists of the blocks in levels of n blocks placed next to each other along their long sides and at a right angle to the previous level. Players remove blocks from the tower in turns, until the tower collapses.

Jane wants to build a game simulator that helps her to decide the best n and w.

The simulator shall compute the moment when the tower collapses if blocks are removed in the specified order. Tower collapses if there is a cross-section between levels such that the center of the mass of the levels above it does not belong to or is at the edge of the convex hull of the previous level projection.

Input file format

The first line contains two integers n and w that define the dimensions of the block as described in the problem statement (1 ≤ n, w ≤ 10 000).

The second line also contains two integers: h — the number of levels in the tower and m — the number of removed blocks (1 ≤ h, m ≤ 5 000).

The next m lines contain coordinates of the removed blocks with two integers each: l_i — the level of the block, counting from the bottom and k_i — the position of the block, counting from the edge nearest to the players (1 ≤ l_i ≤ h; 1 ≤ k_i ≤ n).

Blocks are removed one by one and no block is removed twice.

Output file format

In the first line output «yes» if the tower collapses, and «no» otherwise. In the former case, output the number of the block (starting from 1), that was removed just before the collapse, in the next line.

Constraints

Sample tests

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

yes
5

3 3
10 1
10 3

no

2 2
2 1
1 1

yes
1

Problem 2L. List of Primes ≡

Statement

Lidia likes sets of prime numbers. When she is bored, she starts writing them down into the Extremely Long Notebook for Prime Sets.

Elements of each set are written down in ascending order. Each set of prime numbers appears in her notebook eventually. A set with a smaller sum always appears before a set with a larger sum. Sets with the same sum are sorted in ascending lexicographical order: they are compared by the first element, if the first elements are equal, then by second element, and so on.

Just in case someone decides to parse her notebook, she writes down her sets in a machine-readable JSON format. Of course, she puts a space after each comma. Here's the beginning of her notebook:

[2], [3], [2, 3], [5], [2, 5], [7], [3, 5], [2, 7], [2, 3, 5], [3, 7], [11], [2, 3, 7], [5, 7], [2, 11], [13], [2, 5, 7],

Lidia wants to double-check her work, so here is her request for you: given two integers, a and b, output a substring of her notebook from the position a to the position b (inclusive, counting from 1).

Input file format

The first line contains two integers, a and b (1 ≤ a ≤ b ≤ 10¹⁸; b − a ≤ 10⁵).

Output file format

Output the substring of the notebook described in the problem statement from the position a to the position b. You must write a line with exactly b − a + 1 characters, including any leading and/or trailing spaces.

Constraints

Sample tests

1 35

[2], [3], [2, 3], [5], [2, 5], [7],

36 41

 [3, 5

Problem 3K. King's Inspection ≡

Statement

King Karl is a responsible and diligent ruler. Each year he travels across his country to make certain that all cities are doing well.

There are n cities in his country and m roads. In order to control the travelers, each road is unidirectional, that is a road from city a to city b can not be passed from b to a.

Karl wants to travel along the roads in such a way that he starts in the capital, visits every non-capital city exactly once, and finishes in the capital again.

As a transport minister, you are obliged to find such a route, or to determine that such a route doesn't exist.

Input file format

The first line contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ n + 20) — the number of cities and the number of roads in the country.

Each of the next m lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n), meaning that there is a one-way road from city a_i to city b_i. Cities are numbered from 1 to n. The capital is numbered as 1.

Output file format

If there is a route that passes through each non-capital city exactly once, starting and finishing in the capital, then output n + 1 space-separated integers — a list of cities along the route. Do output the capital city both in the beginning and in the end of the route. If there is no desired route, output «There is no route, Karl!» (without quotation marks).

Constraints

Sample tests

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

1 3 4 2 1

4 3
1 4
1 4
2 2

There is no route, Karl!

Problem 3L. Landscape Improved ≡

Statement

Louis L Le Roi-Univers has ordered to improve the landscape that is seen from the royal palace. His Majesty prefers to see a high mountain.

The Chief Landscape Manager is going to raise a mountain for Louis. He represents a landscape as a flat picture on a grid of unit squares. Some of the squares are already filled with rock, while others are empty. This greatly simplifies the design. Unit squares are small enough, and the landscape seems to be smooth from the royal palace.

The Chief Landscape Manager has a plan of the landscape — the heights of all rock-filled columns for each unit of width. He is going to add at most n square units of stones atop of the existing landscape to make a mountain with as high peak as possible. Unfortunately, piles of stones are quite unstable. A unit square of stones may be placed only exactly on top of the other filled square of stones or rock, moreover the squares immediately to the bottom-left and to bottom-right of it should be already filled.

Your task is to help The Chief Landscape Manager to determine the maximum height of the highest mountain he can build.

Input file format

The first line of the input file contains two integers w — the width of the existing landscape and n — the maximum number of squares of stones to add (1 ≤ w ≤ 100 000, 0 ≤ n ≤ 10¹⁸).

Each of the following w lines contains a single integer h_i — the height of the existing landscape column (1 ≤ h_i ≤ 10⁹).

Output file format

The output file shall contain the single integer — the maximum possible landscape height after at most n unit squares of stones are added in a stable way.

Constraints

Sample tests

8 4
3
4
2
1
3
3
2
4

5

3 100
3
3
3

4

Problem 4H. Hack Protection ≡

Statement

Pavel is sending to his friend Egor some array of non-negative integers. He wants to be sure, that nobody hacks the array before his friend gets it. To solve this problem Pavel need to compute some kind of a checksum or a digest for his array. Pavel has an innovative mind, so he invents the following algorithm to compute the digest for his array: count the number of subarrays in which the bitwise xor of the numbers in the subarray is equal to the bitwise and of the same numbers.

For example, consider an array of four binary numbers “01”, “10”, “11”, and “11”. The table below to the left lists the results of the bitwise xor of numbers for each subarray of this array, and the table below to the right list the results of the bitwise and of numbers for each subarray of this array. The rows of the table correspond to the starting elements of the subarray from the 1st element of the array to the 4th one, while columns correspond to the ending elements of the subarray. Matching values are highlighted with gray background.

Your task is to help Pavel compute this kind of a digest of the given array.

Input file format

The first line contains one integer n (1 ≤ n ≤ 100000). The second line contains n non-negative integers a_i(0 ≤ a_i ≤ 2³¹ − 1) that are written in decimal notation.

Output file format

On the first line of the output print Pavel’s digest of the given array.

Constraints

Sample tests

4
1 2 3 3

6

Problem 4K. Kabaleo Lite ≡

Statement

Kabaleo Lite is a board game. The board consists of several stacks of conical chips of various colors. Only the color of the top chip of the stack is visible.

Each player has a unique target color and a set of colored chips. The target color is hidden from other players, while the set of chips is visible to them. On his turn, player selects one of his chips and puts it on one of the board stacks, thus recoloring it to the color of the chosen chip.

After the last turn, the number of visible board chips of each color is calculated. The winning color is the color that occurs the maximum times. The player (if any) that has this color as his target color, wins the game. If there is no such player or if there are two or more colors that occur the maximum times, the game ends in a draw.

You are playing your last chip in the Kabaleo Lite game. Other players also have one chip left. You want to determine all possible moves that lead you to winning the game. You do not know the target colors of other players and you cannot predict their moves, so your move must guarantee your victory regardless of moves of your opponents.

Input file format

The first line contains four integers n, p, c and h — the number of stacks on the board (1 ≤ n ≤ 10⁶), the number of players (1 ≤ p ≤ 10⁶), the number of chips’ colors (p≤c≤10⁶), and your hidden color (1 ≤ h ≤ c).

The second line contains n integers b_i — the color of the visible board chip for each stack on the board (1 ≤ b_i ≤ c).

The third line contains p integers l_i — the color of the last chip for each player (1 ≤ l_i ≤ c). The players are numbered from one (you) to n in the order of their turns.

Output file format

The first line must contain w — the number of winning moves.

The second line must contain w distinct numbers m_i — the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.

Remember, that your move should be winning regardless of the moves of all other players.

Constraints

Sample tests

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

1
2

Problem 5D. Dictionary Size ≡

Statement

The Kingdom consists of n cities connected by n − 1 roads in such a way that there is exactly one way to travel from one city to another.

The King is a busy man and he constantly travels from city to city. Unfortunately, during one of his travels one of the roads got damaged and needed serious repairs. As a result, the King was unable to reach his destination in time.

After the incident the King decided to improve reliability of the road system. It was decided that the improved road system shall be able to withstand one damaged road, i.e. there shall always be a path from one city to another even when one road in the Kingdom is damaged. As always, the budget is limited so you need to minimize the number of new roads.

For example, the picture below shows 5 Kingdom’s cities numbered from 1 to 5 and roads between them in solid lines. One of the ways to build new roads is shown in dashed lines.

Your task is to build as few new roads as possible so that there is always a path between any two cities even if one of the roads gets unusable for any reason. There may be multiple optimal solutions. Any one can be used.

Input file format

The first line of the input file contains integer n — the number of cities in the kingdom (2 ≤ n ≤ 100000). The following n − 1 lines contain two integers u_i, vi each — the cities connected by i-th road (1 ≤ ui, vi ≤ n).

The first line of the output file shall contain one integer k — the number of roads to be built. The following k lines shall contain two integers a_i, b_i each — the cities which should be connected by i-th new road (1 ≤ ai, bi ≤ n).

Output file format

The first line must contain w — the number of winning moves.

The second line must contain w distinct numbers m_i — the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.

Remember, that your move should be winning regardless of the moves of all other players.

Constraints

Problem 5G. GCD Guessing Game ≡

Statement

Paul had a birthday yesterday, and they were playing a guessing game there with Andrew: Andrew was trying to guess Paul’s age. Andrew knew that Paul’s age is an integer between 1 and n, inclusive. Andrew can guess any number x between 1 and n, and Paul will tell him what is the greatest common divisor of x and his age.

Here’s a possible course of the game for n = 6. Andrew starts with guessing 3, and Paul replies that the greatest common divisor of 3 and his age is 1. That means that Paul’s age can’t be 3 or 6, but can still be 1, 2, 4 or 5. Andrew continues with guessing 2, and Paul replies 2. That means that Paul’s age can’t be 1 or 5, and the only two remaining choices are 2 and 4. Finally, Andrew guesses 4, and Paul replies 2. That means that Paul’s age is 2, and the game is over.

Andrew needed three guesses in the above example, but it’s possible to always determine Paul’s age in at most two guesses for n = 6. The optimal strategy for Andrew is: at the first step, guess 6. If Paul says 1, then its 1 or 5 and he can check which one by guessing 5. If Paul says 2, then its 2 or 4, and he can check by guesing 4 as we’ve seen above. If Paul says 3, then we already know the answer is 3. Finally, if Paul says 6, the answer is 6.

What is the number of guesses required in the worst case if Andrew guesses optimally for the given n?

Input file format

The input file contains one integer n, 2 ≤ n ≤ 10000.

Output file format

Output one integer — the number of guesses Andrew will need to make in the worst case.

Constraints

Sample tests

6

2

Problem 5K. Kingdom Roadmap ≡

Statement

The Kingdom consists of n cities connected by n − 1 roads in such a way that there is exactly one way to travel from one city to another.

The King is a busy man and he constantly travels from city to city. Unfortunately, during one of his travels one of the roads got damaged and needed serious repairs. As a result, the King was unable to reach his destination in time.

After the incident the King decided to improve reliability of the road system. It was decided that the improved road system shall be able to withstand one damaged road, i.e. there shall always be a path from one city to another even when one road in the Kingdom is damaged. As always, the budget is limited so you need to minimize the number of new roads.

For example, the picture below shows 5 Kingdom’s cities numbered from 1 to 5 and roads between them in solid lines. One of the ways to build new roads is shown in dashed lines.

Your task is to build as few new roads as possible so that there is always a path between any two cities even if one of the roads gets unusable for any reason. There may be multiple optimal solutions. Any one can be used.

Input file format

The first line of the input file contains integer n — the number of cities in the kingdom (2 ≤ n ≤ 100000). The following n − 1 lines contain two integers u_i, vi each — the cities connected by i-th road (1 ≤ ui, vi ≤ n).

The first line of the output file shall contain one integer k — the number of roads to be built. The following k lines shall contain two integers a_i, b_i each — the cities which should be connected by i-th new road (1 ≤ ai, bi ≤ n).

Output file format

The first line must contain w — the number of winning moves.

The second line must contain w distinct numbers m_i — the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from 1 in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.

Remember, that your move should be winning regardless of the moves of all other players.

Constraints

Sample tests

5
1 2
2 3
3 4
3 5

2
1 4
4 5

4
1 2
1 3
1 4

2
3 2
1 4