Codeforces Round 362 (Div. 2)
A. Pineapple Incident
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ted has a pineapple. This pineapple is able to bark like a bulldog! At time t (in seconds) it barks for the first time. Then every s seconds after it, it barks twice with 1 second interval. Thus it barks at times t, t + s, t + s + 1, t + 2s, t + 2s + 1, etc.

Barney woke up in the morning and wants to eat the pineapple, but he can't eat it when it's barking. Barney plans to eat it at time x (in seconds), so he asked you to tell him if it's gonna bark at that time.

Input

The first and only line of input contains three integers t, s and x (0 ≤ t, x ≤ 109, 2 ≤ s ≤ 109) — the time the pineapple barks for the first time, the pineapple barking interval, and the time Barney wants to eat the pineapple respectively.

Output

Print a single "YES" (without quotes) if the pineapple will bark at time x or a single "NO" (without quotes) otherwise in the only line of output.

Examples
Input
3 10 4
Output
NO
Input
3 10 3
Output
YES
Input
3 8 51
Output
YES
Input
3 8 52
Output
YES
Note

In the first and the second sample cases pineapple will bark at moments 3, 13, 14, ..., so it won't bark at the moment 4 and will bark at the moment 3.

In the third and fourth sample cases pineapple will bark at moments 3, 11, 12, 19, 20, 27, 28, 35, 36, 43, 44, 51, 52, 59, ..., so it will bark at both moments 51 and 52.

B. Barnicle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Barney is standing in a bar and starring at a pretty girl. He wants to shoot her with his heart arrow but he needs to know the distance between him and the girl to make his shot accurate.

Barney asked the bar tender Carl about this distance value, but Carl was so busy talking to the customers so he wrote the distance value (it's a real number) on a napkin. The problem is that he wrote it in scientific notation. The scientific notation of some real number x is the notation of form AeB, where A is a real number and B is an integer and x = A × 10B is true. In our case A is between 0 and 9 and B is non-negative.

Barney doesn't know anything about scientific notation (as well as anything scientific at all). So he asked you to tell him the distance value in usual decimal representation with minimal number of digits after the decimal point (and no decimal point if it is an integer). See the output format for better understanding.

Input

The first and only line of input contains a single string of form a.deb where a, d and b are integers and e is usual character 'e' (0 ≤ a ≤ 9, 0 ≤ d < 10100, 0 ≤ b ≤ 100) — the scientific notation of the desired distance value.

a and b contain no leading zeros and d contains no trailing zeros (but may be equal to 0). Also, b can not be non-zero if a is zero.

Output

Print the only real number x (the desired distance value) in the only line in its decimal notation.

Thus if x is an integer, print it's integer value without decimal part and decimal point and without leading zeroes.

Otherwise print x in a form of p.q such that p is an integer that have no leading zeroes (but may be equal to zero), and q is an integer that have no trailing zeroes (and may not be equal to zero).

Examples
Input
8.549e2
Output
854.9
Input
8.549e3
Output
8549
Input
0.33e0
Output
0.33

C. Lorenzo Von Matterhorn
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Barney lives in NYC. NYC has infinite number of intersections numbered with positive integers starting from 1. There exists a bidirectional road between intersections i and 2i and another road between i and 2i + 1 for every positive integer i. You can clearly see that there exists a unique shortest path between any two intersections.

Initially anyone can pass any road for free. But since SlapsGiving is ahead of us, there will q consecutive events happen soon. There are two types of events:

1. Government makes a new rule. A rule can be denoted by integers v, u and w. As the result of this action, the passing fee of all roads on the shortest path from u to v increases by w dollars.

2. Barney starts moving from some intersection v and goes to intersection u where there's a girl he wants to cuddle (using his fake name Lorenzo Von Matterhorn). He always uses the shortest path (visiting minimum number of intersections or roads) between two intersections.

Government needs your calculations. For each time Barney goes to cuddle a girl, you need to tell the government how much money he should pay (sum of passing fee of all roads he passes).

Input

The first line of input contains a single integer q (1 ≤ q ≤ 1 000).

The next q lines contain the information about the events in chronological order. Each event is described in form 1 v u w if it's an event when government makes a new rule about increasing the passing fee of all roads on the shortest path from u to v by w dollars, or in form 2 v u if it's an event when Barnie goes to cuddle from the intersection v to the intersection u.

1 ≤ v, u ≤ 1018, v ≠ u, 1 ≤ w ≤ 109 states for every description line.

Output

For each event of second type print the sum of passing fee of all roads Barney passes in this event, in one line. Print the answers in chronological order of corresponding events.

Example
Input
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
Output
94
0
32
Note

In the example testcase:

Here are the intersections used:

  1. Intersections on the path are 3, 1, 2 and 4.
  2. Intersections on the path are 4, 2 and 1.
  3. Intersections on the path are only 3 and 6.
  4. Intersections on the path are 4, 2, 1 and 3. Passing fee of roads on the path are 32, 32 and 30 in order. So answer equals to 32 + 32 + 30 = 94.
  5. Intersections on the path are 6, 3 and 1.
  6. Intersections on the path are 3 and 7. Passing fee of the road between them is 0.
  7. Intersections on the path are 2 and 4. Passing fee of the road between them is 32 (increased by 30 in the first event and by 2 in the second).

D. Puzzles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Barney lives in country USC (United States of Charzeh). USC has n cities numbered from 1 through n and n - 1 roads between them. Cities and roads of USC form a rooted tree (Barney's not sure why it is rooted). Root of the tree is the city number 1. Thus if one will start his journey from city 1, he can visit any city he wants by following roads.

Some girl has stolen Barney's heart, and Barney wants to find her. He starts looking for in the root of the tree and (since he is Barney Stinson not a random guy), he uses a random DFS to search in the cities. A pseudo code of this algorithm is as follows:


let starting_time be an array of length n
current_time = 0
dfs(v):
	current_time = current_time + 1
	starting_time[v] = current_time
	shuffle children[v] randomly (each permutation with equal possibility)
	// children[v] is vector of children cities of city v
	for u in children[v]:
		dfs(u)

As told before, Barney will start his journey in the root of the tree (equivalent to call dfs(1)).

Now Barney needs to pack a backpack and so he wants to know more about his upcoming journey: for every city i, Barney wants to know the expected value of starting_time[i]. He's a friend of Jon Snow and knows nothing, that's why he asked for your help.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 105) — the number of cities in USC.

The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi < i), where pi is the number of the parent city of city number i in the tree, meaning there is a road between cities numbered pi and i in USC.

Output

In the first and only line of output print n numbers, where i-th number is the expected value of starting_time[i].

Your answer for each city will be considered correct if its absolute or relative error does not exceed 10 - 6.

Examples
Input
7
1 2 1 1 4 4
Output
1.0 4.0 5.0 3.5 4.5 5.0 5.0
Input
12
1 1 2 2 4 4 3 3 1 10 8
Output
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0

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

As we all know Barney's job is "PLEASE" and he has not much to do at work. That's why he started playing "cups and key". In this game there are three identical cups arranged in a line from left to right. Initially key to Barney's heart is under the middle cup.

Then at one turn Barney swaps the cup in the middle with any of other two cups randomly (he choses each with equal probability), so the chosen cup becomes the middle one. Game lasts n turns and Barney independently choses a cup to swap with the middle one within each turn, and the key always remains in the cup it was at the start.

After n-th turn Barney asks a girl to guess which cup contains the key. The girl points to the middle one but Barney was distracted while making turns and doesn't know if the key is under the middle cup. That's why he asked you to tell him the probability that girl guessed right.

Number n of game turns can be extremely large, that's why Barney did not give it to you. Instead he gave you an array a1, a2, ..., ak such that

in other words, n is multiplication of all elements of the given array.

Because of precision difficulties, Barney asked you to tell him the answer as an irreducible fraction. In other words you need to find it as a fraction p / q such that , where is the greatest common divisor. Since p and q can be extremely large, you only need to find the remainders of dividing each of them by 109 + 7.

Please note that we want of p and q to be 1, not of their remainders after dividing by 109 + 7.

Input

The first line of input contains a single integer k (1 ≤ k ≤ 105) — the number of elements in array Barney gave you.

The second line contains k integers a1, a2, ..., ak (1 ≤ ai ≤ 1018) — the elements of the array.

Output

In the only line of output print a single string x / y where x is the remainder of dividing p by 109 + 7 and y is the remainder of dividing q by 109 + 7.

Examples
Input
1
2
Output
1/2
Input
3
1 1 1
Output
0/1

F. Legen...
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Barney was hanging out with Nora for a while and now he thinks he may have feelings for her. Barney wants to send her a cheesy text message and wants to make her as happy as possible.

Initially, happiness level of Nora is 0. Nora loves some pickup lines like "I'm falling for you" and stuff. Totally, she knows n pickup lines, each consisting only of lowercase English letters, also some of them may be equal (in writing, but different in pronouncing or meaning though). Every time Nora sees i-th pickup line as a consecutive subsequence of Barney's text message her happiness level increases by ai. These substrings may overlap, for example, Nora will see the pickup line aa twice and the pickup line ab once in text message aaab.

Due to texting app limits, Barney's text may have up to l characters.

Barney asked you to help him make Nora as much happy as possible, it's gonna be legen...

Input

The first line of input contains two integers n and l (1 ≤ n ≤ 200, 1 ≤ l ≤ 1014) — the number of pickup lines and the maximum length of Barney's text.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100), meaning that Nora's happiness level increases by ai after every time seeing i-th pickup line.

The next n lines contain the pickup lines. i-th of them contains a single string si consisting of only English lowercase letter. Summary length of all pickup lines does not exceed 200.

All strings are not empty.

Output

Print the only integer — the maximum possible value of Nora's happiness level after reading Barney's text.

Examples
Input
3 6
3 2 1
heart
earth
art
Output
6
Input
3 6
3 2 8
heart
earth
art
Output
16
Note

An optimal answer for the first sample case is hearth containing each pickup line exactly once.

An optimal answer for the second sample case is artart.