2018 UBC Winter Contest 3
A. Amazing Chef Masters
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Amazing Chef Masters (ACM) have annual contests to determine the rankings of the members. Each chef has a skill level that could change over the years. Since each chef is a different individual, no two chefs will ever have the same skill level. The annual rankings are always based on the skill levels, so no ties will occur. More precisely, if chef A has a higher skill level than chef B, then chef A will have a better rank than chef B.

Usually the chefs would have a detailed record of the skill levels of the members each year, however, they were attacked by the Attacking Cactus Monsters (ACM)! These monstrous beings stole all of the records except the annual rankings.

Now the chefs want to regain some information about their skill levels. Given the rankings of two consecutive years, the chef masters would like to know the maximum possible number of chefs whose skill levels did not change.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 105), the number of chefs in ACM.

The second line of input contains n distinct space-separated integers ai (1 ≤ ai ≤ n), describing the rank of the chefs in the first year. The aith chef has rank i in the first year.

The third line of input contains n distinct space-separated integers bi (1 ≤ bi ≤ n), describing the rank of the chefs in the second year. The bith chef has rank i in the second year.

Output

Print one integer that is the maximum possible number chefs whose skill levels did not change.

Example
Input
4
2 3 1 4
3 2 1 4
Output
3
Note

This is the explanation for the sample. In the first year, chef 2 is ranked first, chef 3 is ranked second, chef 1 is ranked third, and chef 4 is ranked fourth. In the second year, chef 3 is ranked first, chef 2 is ranked second, chef 1 is ranked third, and chef 4 is ranked fourth. We can get the answer 3 by letting chefs 1, 3, and 4 have skill levels that remained unchanged, while chef 2's skill decreases.

B. Badminton
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A little green Cactus is secretly in charge of a badminton club, and he wants to enter four members in the next tournament. There is a total of n members in the club. Each member has a playing style and a strength ai. To make the team of four well rounded, Cactus wants at least one member of each playing style on the team. Cactus also wants his team to win the tournament, so he will only consider teams whose strength is at least k. The strength of a team is the average of the strengths of the four individuals.

Cactus wants to know the number of distinct teams of four whose strength is at least k and contains at least one member of each of the three playing styles. Two teams are considered different if there exists a member who is in exactly one of them.

Input

The first line contains two space-separated integers n and k (2 ≤ n ≤ 3000;1 ≤ k ≤ 105), the number of members in the club, and the minimum acceptable team strength respectively.

Each of the next n lines contains two space-separated integers ti and ai (1 ≤ ti ≤ 3;1 ≤ ai ≤ 105), describing the ith member. That is the ith member has playing style ti and strength ai.

Output

Print a single integer representing the number of distinct teams that satisfy the two conditions.

Example
Input
6 3
1 2
1 2
2 2
3 1
3 3
3 7
Output
5

C. Cakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Our friend, the little Cactus, has n stacks of cakes and an integer k. Initially, the n stacks of cakes have sizes 1, 2, ..., n, that is the ith stack has i cakes. For aesthetic reasons, Cactus wants to make a large stack of cakes. Cactus can perform up to 105 operations on the n stacks.

Let si denote the size of the ith stack. Each operation consists of 3 steps.

  1. Cactus chooses an integer a where 2 ≤ a ≤ k.
  2. Cactus chooses two stacks A and B, where sA ≥ (a - 1)·sB.
  3. Cactus moves (a - 1)·sB cakes from stack A to stack B.
Now Cactus wants to know the size of the largest possible stack he could make. However, Cactus likes surprises, so he wants you to tell him the operations he should perform to make the largest possible stack.
Input

The first line contains two space separated integers n and k (1 ≤ n ≤ 200, 2 ≤ k ≤ 12).

Output

In the first line, output a single integer x representing the number of operations Cactus should perform.

For each of the next x lines, output two space separated integers yi, zi, and ti, representing an operation where Cactus should choose the integer ti, and move cakes from stack yi to stack zi.

Your solution will be considered correct if 0 ≤ x ≤ 105, each operation is valid, and the largest possible stack that could be made this way is one of the n stacks after performing all the operations.

If there are multiple solutions, output any of them.

Example
Input
6 3
Output
7
6 3 3
4 2 3
3 5 2
2 1 2
3 1 3
1 2 2
2 5 2

D. Dessert First Strategy
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dessert First Strategy (DFS) refers to the strategy to monopolize the dessert before other people have a chance to get to it. This usually involves an elaborate plan with various positions that should be occupied by units.

More precisely, there are n positions that form a tree. Each position is one of k roles, labeled from 1 to k inclusive. You have an unlimited number of each of the two available types of units (tourist and cactus) to assign to the positions. However, you must assign the same unit within each role. That is, if you assign a tourist to a position of role 1, then you cannot assign a cactus to another position of role 1.

Each of the two units has a list of valid roles they can take (for example, cacti cannot take the role that is messenger pigeon). It is guaranteed that each role can be taken by at least one of the two units. Now, it is always possible to assign units to positions based on the aforementioned restrictions.

The n positions form a tree, and each edge has an effectiveness value ci. This effectiveness can be gained if the two units assigned to the positions adjacent to the edge are the same type, in which case the effectiveness of the edge is ci. If the two units are not the same type, then the effectiveness of the edge is 0. The effectiveness of the strategy is the sum of the effectivenesses of each edge.

Given the number of positions, the number of roles, and the shape of the tree, calculate the maximum possible effectiveness that could be obtained by assigning units to the roles optimally.

Input

The first line of input contains four space-separated integers n, k, p, q (1 ≤ n ≤ 105;1 ≤ p, q ≤ k ≤ 200), representing the number of positions, the number of communications, and the number of roles respectively.

The second line of input contains p distinct space-separated integers each between 1 and k inclusive, representing the roles that the tourists can take.

The third line of input contains q distinct space-separated integers each between 1 and k inclusive, representing the roles that the cacti can take.

The fourth line contains n space-separated integers. The ith integer ri represents the role of the ith position.

Each of the next n - 1 lines contains three space-separated integers ai, bi, and ci (1 ≤ a < b ≤ n;1 ≤ ci ≤ 104), describing the ith edge that is between positions ai and bi with a possible effectiveness gain of ci.

Output

Output a single integer representing the maximum effectiveness that can be gained.

Example
Input
5 3 2 2
1 2
2 3
1 1 2 1 3
1 2 2
2 3 3
3 4 1
4 5 42
Output
6
Note

In the first sample, it is optimal to have the tourists take roles 1 and 2 while the cacti take role 3. This means we get the following effectiveness gains:

  • 2 effectiveness from 1 and 2
  • 3 effectiveness from 2 and 3
  • 1 effectiveness from 3 and 4

E. Easy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

E for Easy.

Clearly, E for Easy sounds better than D for Deasy, F for Feasy, G for Geasy, or other such nonsense. Perhaps less clear is that E for Easy also sounds better than E for Empossible. It follows that the only logical title for this problem is Easy. Whether this problem is actually easy is up to you.

It is 23:16. The relentless rain pelting my window keeps me awake while I write this unintelligible mess. Although my fingers are moving across the k keys of the keyboard and pressing r keys that somehow translate to s complete albeit meaningless words, my mind is elsewhere. The rain outside just made me remember that nightmare I had w days ago. I was chasing my sanity down a network of p dank alleyways of some ghost town in the middle of a desert. My sanity was somewhere ahead of me, just outside of my reach. But this was only the prelude to the nightmare. As I chased my fleeing sanity into a tavern, I came face to face with a 40cm tall messenger pigeon. Frightened out of my wits, I awoke to the sound of birds chirping as if nothing had happened. Unfortunately, my sanity is still hiding inside the tavern.

The tavern has n rooms that are connected by m bidirectional halls. The n rooms are uniquely labeled with integers from 1 to n inclusive. The pigeon is in room 1, and my sanity is in room n. Each of the m halls require a certain amount of time to traverse. Even someone like me is able to follow these halls from 1 to n in the minimum amount of time possible. However, there are traps in each hall! Now, each hall only has an interval of time when it is safe to be in it. Should one set foot in a hall when it is unsafe, unthinkable things will happen.

I am unable to solve such a difficult problem, so it is up to you to determine the shortest amount of time it takes to go from the room where the pigeon is at to the room where my sanity is hiding. It is now time 0, let the search begin!

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 2·105;1 ≤ m ≤ 2·105), representing the number of rooms and halls respectively.

Each of the next m lines contains five space-separated integers ai, bi, ci, di, and ti (1 ≤ ai, bi ≤ n;0 ≤ ci < di ≤ 109;1 ≤ ti ≤ 109), describing the ith hall. This means the ith hall is between rooms ai and bi, it is safe to be in the hall from time ci to time di inclusive and it takes ti minutes to traverse the hall (in either direction). Two rooms could be connected by multiple halls. It is guaranteed that ai ≠ bi.

Output

Output a single integer representing the shortest time it takes to go from room 1 to room n if it is possible to safely reach room n, or output -1 otherwise.

Examples
Input
3 3
1 2 4 10 3
2 3 19 42 5
1 3 1 7 7
Output
24
Input
3 2
1 2 14 17 1
2 3 12 15 1
Output
-1
Note

In the first sample, the only way to reach the destination is by taking the halls from 1 to 2 and from 2 to 3. The journey can be as follows.

  1. Time 0-4, wait 4 minutes in room 1
  2. Time 4-7, take the hall from 1 to 2
  3. Time 7-19, wait 12 minutes in room 2
  4. Time 19-24, take the hall from 2 to 3

F. Farmer Faul
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Faul decided to become a farmer, and he grows bamboo!

Faul has n bamboo stalks numbered from 1 to n, and he can do three operations on them. He can cut and harvest all of the bamboo at a certain height, order a single bamboo stalk to grow, or use magic to make all bamboo stalks grow.

Faul knows exactly what his next q operations will be. Each operation will be one of the three types.

  • CUT h. Faul cuts all the bamboo stalks at height h (1 ≤ h ≤ 106). More precisely, if a stalk is higher than height h, then the part higher than h will be cut off and harvested. For this query, you should output one integer, on a line by itself, representing the total length of bamboo harvested by this cut.
  • GROW i x. Faul orders the ith stalk to grow by x (1 ≤ i ≤ n;1 ≤ x ≤ 106). More precisely, if stalk i was at height k, then this query makes it grow to height k + x.
  • MAGIC y. Faul uses magic to make all bamboo stalks grow by y (1 ≤ y ≤ 106).

Since Faul has more important things to tend to (such as badminton), he wants you to help him predict the amount of bamboo he will harvest after each cut.

Input

The first line of input contains two space-separated integers n and q (1 ≤ n ≤ 106;1 ≤ q ≤ 106).

The second line of input contains n space-separated integers hi (1 ≤ hi ≤ 106), where hi is the initial height of the ith bamboo stalk.

Each of the next q lines contains a query. Each query is one of the three aforementioned types.

Output

For each CUT query, output a single integer, on a line by itself, that is the total length of bamboo harvested by that cut.

Example
Input
4 5
1 2 3 3
GROW 3 1
CUT 2
MAGIC 2
CUT 2
CUT 7
Output
3
7
0
Note

In the first sample, we do the following.

  • GROW 3 1. We grow the third bamboo by 1. Now the heights are 1 2 4 3.
  • CUT 2. We cut everything at height 2, so we cut 2 and 1 units from the third and fourth bamboos respectively. We output 3 since 1 + 2 = 3. Now the heights are 1 2 2 2.
  • MAGIC 2. We grow all the bamboos by 2. Now the heights are 3 4 4 4.
  • CUT 2. We cut everything at height 2. We cut 1 unit from bamboo 1, and we cut 2 units from bamboos 2, 3, and 4. We output 7 since 1 + 2 + 2 + 2 = 7. Now the heights are 2 2 2 2.
  • CUT 7. We cut everything at height 7. No bamboo is higher than 7 so nothing is cut. We output 0 and the heights remain unchanged.

G. Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Our little Cactus friend is back with an interesting game! This game features a wheel which consists of n compartments connected in a loop. Each compartment has a hole leading out of the loop. To play, the ball is randomly put into one of the compartments, and the player simply watches it roll around the loop. After some time, the ball will exit through one of the holes, and the game ends. Once the ball exists the wheel, the player is given a score based on the hole from which it exited, and the compartments that the it had visited (counting multiplicity).

More precisely, if the ball is at compartment i for 1 ≤ i < n, it may exit the wheel with probability pi or it may move on to compartment i + 1 with probability 1 - pi. If the ball is at compartment n, it may exit the wheel with probability pn or move on to compartment 1 with probability 1 - pn. The player begins with a score of 0. Each time the ball visits compartment i, the player gains ai score. If the last compartment the ball was in before it exited the loop was compartment j, the player gains an additional bj score.

All that is left is for Cactus to assign probabilities. To make things interesting, he wants to assign probabilities so that 0.01 ≤ pi ≤ 0.99. Since the score counting contraption cannot handle very large numbers, Cactus wants to minimize the expected score. Your task is to calculate the minimum possible expected score while the probabilities satisfy the given restriction. You may assume that the initial compartment is chosen uniformly at random.

Input

The first line of input contains a single integer n (2 ≤ n ≤ 500), the number of compartments in the wheel.

Each of the next n lines contains two space-separated integers ai and bi, (1 ≤ ai, bi ≤ 106), describing the ith compartment. ai is the score gained each time the ith compartment is visited, and bi is the score gained if the ith compartment is the last compartment visited.

Output

Print, on a single line, the minimum possible expected score. Your answer will be considered correct if it is within 10 - 6 absolute or relative error.

Examples
Input
3
1 100
1 100
1 1
Output
4.0227937347
Input
2
420 3
1 1
Output
214.6262626263

H. Hiking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cactus is hiking with his friends in the Great Bear Rainforest. As they were too busy practicing ACM problems the night before, they forgot to bring bug spray, emergency shelter, whistles, and most importantly, food! After several dozen hours, Cactus and his friends become tired and hungry. Suddenly, Cactus spots a berry on a bush. Just as he stretches out his hand to pick it, he hears a low grumbling noise behind him. It's a Great Bear, and it's hungry... for berries!

Thinking quickly, Cactus pulls out his M4 Carbine with a M203 grenade launcher attachment and blasts the Great Bear into the Spirit Realm. Unfortunately, he forgot to stock up on bullets and grenades, so he has no projectiles left. In his panic, Cactus asks the Geometry God to estimate the probability of their survival. Clearly this is an insult to Geometry's intelligence and omnipotence, as he immediately gives Cactus the exact probability of their survival as a function of the amount of time it takes them to leave the Great Bear Rainforest.

In this equation, e is Euler's constant and t is the time it will take Cactus and his friends to escape from the Great Bear Rainforest. P(t) gives the percent probability that the group manages to leave untraumatized.

Given this equation, Cactus is faced with the impossible task of finding t. Luckily, Cactus knows exactly how long it will take them to exit the Great Bear Rainforest from his primal instincts as a Great Bear warrior in his previous life.

Due to a lack of food and safety blankets, Cactus is too hungry to think straight. Help Cactus and his friends find the probability that they will survive, and not be bearied by barely beary barbearian berry bears bearfacedly bearing down on them!

Input

The only line of input contains one integer t (1 ≤ t ≤ 106).

Output

Output P(t) for the given time. Your answer will be considered correct if the absolute error is at most 10 - 3.

Example
Input
1
Output
98.9283067805

I. LASER SHIELDs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Our green Cactus friend is in danger again! A hostile troop of cacti is trying to attack this lonely cactus. Luckily, Cactus happens to have N LASER SHIELDs. However, Cactus can only activate up to k LASER SHIELDs, and he wants you to help him determine the best way to use k LASER SHIELDs.

Each LASER SHIELD has an activation time ti at which it can be activated. If it is not activated at that time, it loses its power and becomes useless forever. Each LASER SHIELD has an initial power pi and a corrosion rate ri. When a LASER SHIELD is activated, it will have the initial power pi and lose power at the rate of ri power units per second. When the power of a LASER SHIELD drops below 0, it becomes inactive and cannot be used again.

Define the defense power at a specific time to be the maximum power over all activated shields. The defense power is 0 if there are no active shields. Define the protection of Cactus to be the minimum defense power at any time during the attack.

Cactus used w3m to look into the future, seeing that the hostile cacti begin their attack at time ts and end their attac at time te. Your task is to determine the maximum possible protection of Cactus.

Input

The first line contains a two space-separated integers n and k (0 ≤ n, k ≤ 105), the total number of LASER SHIELDs and the number of LASER SHIELDs that Cactus can activate respectively.

Each of the next n lines contains three space-separated integers ti, pi, and ri (0 ≤ ti ≤ 109;1 ≤ pi, ri ≤ 109), describing the ith LASER SHIELD.

The last line of input contains two space-separated integers ts and te (0 ≤ ts < te ≤ 109), the start and end times of the attack respectively.

Output

Print, on a single line, the maximum possible that can be achieved.

Example
Input
4 3
2 10 4
3 6 1
7 3 1
8 12 1
4 9
Output
2
Note

In the first sample, it is optimal to activate the second, third, and fourth shields.

J. Journey
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The little green Cactus is on his daily run through the cactus desert. As usual, he is coding problem J as he runs. However, he forgot his charger today, and his computer is running out of battery. Now Cactus must run from point A (his current location) to point B (the location of his charger).

There are n oddly rectangular cacti in the desert, and Cactus cannot run through these cacti. No two cacti overlap, but they may touch at a point or on a line segment. Cactus cannot run through the points where two cacti touch. Find the minimum distance that Cactus must run to get from A to B.

Input

The first line of input contains a single integer n (0 ≤ n ≤ 100), the number of cacti.

Each of the next n lines contains four space-separated integers ai, bi, xi, and yi ( - 106 ≤ ai < xi ≤ 106; - 106 ≤ bi < yi ≤ 106), describing the bottom left and the top right corners of the cactus (on the Cartesian plane).

The last line of input contains four space-separated integers Ax, Ay, Bx, By ( - 106 ≤ Ax, Ay, Bx, By ≤ 106), describing point A and point B. It is guaranteed that A and B do not lie in the interior or on the boundary of a cactus.

Output

Print the minimum distance Cactus must run, or  - 1 if he cannot run from A to B. The answer will be considered correct if the relative or absolute error is at most 10 - 6.

Example
Input
3
0 0 1 1
0 1 1 2
1 -1 5 0
0 -1 2 1
Output
5.4142135624