VIII Open Programming Championship of Kazan Federal University 2015
A. Polycarp and Digits
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp decided to get into the maze. The maze consists of N rooms connected by N - 1 corridors. In the beginning he is in the room 1, from which he can go to any other. While being in one of the rooms he tries to go to the one where he hasn't been yet. If there are no such rooms, Polycarp goes to the room where he came from or exits from the maze if he is in the room 1 and visited all other rooms. In each room there is an integer. Polycarp defined that in the room i recorded the number ai, repeated bi times. For example, if ai equal to 123 and bi equal to 3, the number will look like 123123123. Every time visiting another room, Polycarp writes the number specified number of times to his notepad. Besides it is considered that in the beginning Polycarp visits room 1. Therefore, he gets one more integer c, composed from all written numbers to the notepad. Polycarp is interested in all subsequences of the consecutive identical digits. Among these subsequences he chooses those who have the greatest length, and among the he chooses the one that is composed of the least digit. He needs to determine from what minimum digit and maximum length it is possible to construct such a subsequence.

Input

The first line contains integer N — the number of rooms. 1 ≤ N ≤ 100000. The following N lines contain pairs of integers separated by spaces: ai and bi. 1 ≤ ai ≤ 100 000, 1 ≤ bi ≤ 1000. In next N - 1 lines there are pairs of integers fi и ti — description of the corridors. Corridor i connects room fi with room ti. Polycarp checks the unvisited rooms in a sequence, written in the input file.

Output

In the first line print two numbers — the minimal digit that appears sequentially more often in c, and how many times it occurs.

Examples
Input
3
11211 1
11111 1
11111 1
1 2
1 3
Output
1 9
Input
3
3 1
3 3
3 7
1 2
1 3
Output
3 13
B. Polycarp and Polynoms
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp has array of N integers a1, ..., aN. Polycarp makes experiments, he applies specific commands. There are M commands of three types. First one follows the form: 1 L R, it means we should decrease by 1 the numbers from array with indexes L, ..., R. Second one follows the form: 2 L R, it means we should increase by 1 the numbers from array with indexes L, ..., R. Third one follows the form: 3 L R a0 a1 a2 a3 a4, it means we should compute , for f(xi) = a0·xi4 + a1·xi3 + a2·xi2 + a3·xi1 + a4 and xi is number form array with index i. You should execute all given commands.

It is garantied that numbers in array always lesser than 201 and greater than  - 201, and any sums from  - 1018 to 1018.

Input

The first line contains integer N — the number of integers in array (1 ≤ N ≤ 105). The first line contains a1, ..., aN — initial numbers in array. The third line contains integer M — the number of commands (1 ≤ M ≤ 105). M lines follow, each containing description of commands. Format is decribed above. 1 ≤ L ≤ R ≤ N,  - 100 ≤ a0, a1, a2, a3, a4 ≤ 100.

Output

Output result for each commands of third type in separated lines.

Examples
Input
5
1 2 3 4 5
7
3 1 5 0 0 0 0 1
3 1 5 0 0 0 1 0
3 1 5 0 0 1 0 0
3 1 5 0 1 0 0 0
3 1 5 1 0 0 0 0
1 1 5
3 1 5 1 0 0 0 0
Output
5
15
55
225
979
354
Input
5
1 2 3 4 5
5
1 1 5
1 1 5
1 1 5
3 1 5 0 1 0 1 0
3 1 5 1 0 1 0 5
Output
0
69
C. Polycarp and Polygon
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp has N segments, where length of i-th one is ai. He wants to find the minimal radius R of a circle, such that we can construct a convex polygon from the segments, all vertexes of the polygon belongs to circumference of the circle, and center of the circle is inside the polygon. You should find that radius, if it is possible.

Input

The first line contains N — the number of segments (3 ≤ N ≤ 100). The second line contains N integer numbers ai — the lengthes of segments (1 ≤ ai ≤ 100).

Output

Output the minimal radius R. If it is not exists then output -1. You may assume that answers is coparated with the precision of 10 - 6.

Examples
Input
3
100 100 100
Output
57.73502737
Input
3
100 51 51
Output
-1
Input
3
100 100 51
Output
51.70946020
D. Polycarp and the Table
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp decided to help to organize the Contest and create logins for each team. He has got a table consisting of N + 1 rows and M columns in the CSV format. It means that the table looks like a text which consists of N + 1 lines. Each line i is written as "ai, 1;ai, 2;... ;ai, m" (without quotations), where ai, j — cell content at the intersection of the row i and the column j. Each cell content corresponds to the line 1 to 30 signs long. A cell can contain only small and capital Latin letters and digits. The first line contains the names of the columns. They always contain "Team", "City", "Email", "Organization", "Participant1", "Participant2" and "Participant3" — team name, city, email address, organization name and participant name respectivly. Columns can be arranged in any order.

Polycarp has to make one more table in the same format including the table fields "Team", "Login", "Email", "Participants" — team name, login, email address and participants respectivly. The login looks like "team<XXX> (<Organization>, <City>)", where <XXX> — three-figure number of the team in the origina table, Organization and City — organization and city names respectivly. The participants complete it as follows: "<Participant1>,<Participant2>,<Participant3>" — participants’ names comma separated.

Input

The table looks like a table consisting of N + 1rows and M columns. 1 ≤ N ≤ 100, 1 ≤ M ≤ 15. The format of data is given in the statement.

Output

The table consists of N + 1 rows in the format given in the statement.

Examples
Input
Country;Organization;City;Team;Email;
Participant1;Participant2;
Participant3$
Russia;KFU;Kazan;KFU01;team01;P1;P2;
P3$
Russia;KFU;Kazan;KFU02;team02;P4;P5;
P6$
Russia;KFU;Kazan;KFU03;team03;P7;P8;
P9$
Russia;ITMO;SaintPetersburg;ITMO00;
somefakemail;I1;I2;I3$
Output
Team;Login;Email;Participants$
KFU01;team001 (KFU, Kazan);team01;
P1,P2,P3$
KFU02;team002 (KFU, Kazan);team02;
P4,P5,P6$
KFU03;team003 (KFU, Kazan);team03;
P7,P8,P9$
ITMO00;team004 (ITMO, SaintPetersburg);
somefakemail;I1,I2,I3$
Note

Line breaks in the example are marked using $, due text does not fit in the page.

E. Polycarp and Arcolygon
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp has got a plane with N circles on it and an infinitely long thread. Each circle i is discribed using the centerpoint coordinates xi and yi and the radius ri. Polycarp uses the thread to swift all the circles so that all of them are inside the figure, formed by the thread. However, the thread can not be cut.

Polycarp is eager to know what the shortest length the tread should be to be able to swift the circles and what area the resulting figure will have.

Input

The first line contains the only integer N, 2 ≤ N ≤ 100.

Next N lines contain integer triplet xi, yi, ri. The numbers are separated by whitespaces,  - 1000 ≤ xi, yi ≤ 1000, 1 ≤ ri ≤ 100. It is insured that the circles do not intersect and contact with each other.

Output

Output two numbers — thread length and figure area. You may assume that answers is coparated with the precision of 10 - 6.

Examples
Input
2
0 0 1
99 99 100
Output
670.80969437 33561.73030009
Input
2
10 0 4
-10 0 4
Output
65.13274123 210.26548246
Input
5
0 100 10
-100 -20 10
100 -20 10
-50 40 10
50 40 10
Output
575.24184011 17438.25913572
F. Polycarp and Satellites
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp likes build space satellites. He learned ideas of projects from Provectus Inc. He knows, that one big satellite is very expensive and is requred to launch a rocket, but N small satellites is cheaper and you can launch satellites, just using special airplane. In that case Polycarp should organize a transmission of data among satellites. He can make two way channel of data transmission between any two different satellites. But a channel requires to install expensive devices on satellites and therefore Polycarp wants to make at most 4·N channels to his satellites. Between any pair of satellites can not be more than 1 channel.

Polycarp wants to know which pairs of satellites he should connect with channels, such that if any K channels are destroyed, then we can find path from any satellite to any another one maybe via other satellites.

Input

The input contains only one line with two integer numbers N and K: 3 ≤ N ≤ 20, 1 ≤ K ≤ 5. Solution always exists.

Output

The first line contains M — the number of channels. M lines follow, each contains ai and bi — numbers of satellites are connected by i channel, M ≤ 4·N.

Examples
Input
5 2
Output
8
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
Input
6 2
Output
9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
G. Polycarp and Palindromes
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identically right to left and left to right. But it is not enough for Polycarp: he can change the signs in the string. Polycarp is eager to know if it is possible to know and define very quickly if the substring of the string S is a palindrome if the letters in S can be substituted. Polycarp conducts K operations one after another.

Input

There is string S in the first line. Its length is N, 1 ≤ N ≤ 100000. S consists of only small Latin letters.

The second line contains the only integer K, 1 ≤ K ≤ 100000 — the number of operations.

Next K lines contain the descriptions of operations, one in each line. Each line starts with the integer ti, which can take the values 1 and 2. If ti equals 1, two integers li and ri, 1 ≤ li ≤ ri ≤ N follow it. It means — it is necessary to define if the substring slisli + 1... sri is a palindrome. If ti equals 2, it is followed by the integer pi and a small Latin letter ci. It means — to substitute in the string S sign in position pi to ci

Output

Output "YES" in separate lines for each operation of the palindrome definition if the substring is a palindrome, or "NO", if it isn’t (without quotations).

Examples
Input
ababaccc
8
1 1 5
1 1 8
1 2 4
2 5 b
2 6 a
2 7 b
2 8 a
1 1 8
Output
YES
NO
YES
YES
Input
aaaa
10
1 1 1
1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 3
1 3 4
1 4 4
Output
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
H. Polycarp and Chains
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp has got a set of N slots, there is one adornment in each slot. Each adornment has got a peculiar number — integer within the interval [1... N]. Polycarp has also got a set of M base and K compound operations. Base operations are called chains. Each chain with the number i is set by the number bli and numbers bi, 1, ..., bi, bli. All bi, j numbers are integers, they are different for each chain and belong to the interval [1... N]. It means the following: the adornment from the position bi, j goes to position bi, j + 1 for 1 ≤ j < bli. The adornment from the position bi, bli goes to position bi, 1. Compound operation with number i is described as follows: numbers cli and cli of a couple of numbers coi, j and cci, j are selected. Each couple means to use the chain coi, j cci, j times.

Polycarp carries out experiments with this set. Before starting each experiment the i-th adornment is placed into slot i. The experiment i is described by eli and eli couple of numbers eoi, j and eci, j. Each couple means to use the compound operation eoi, j eci, j times. Polycarp is eager to know what there will be in each slot after the recurrent experiment is carried out.

Input

The first line contains integer N, 1 ≤ N ≤ 100 — the number of slots and adornments.

The second line contains integer M, 1 ≤ M ≤ 100 — the number of chains. The descriptions of the chains are in the next M lines. The chain is described by bli, 1 ≤ bli ≤ N and different integers bi, j within the interval [1... N].

The next line contains integer K, 1 ≤ K ≤ 100 — the number of compound operations. Their descriptions are in the next lines. Each compound operation is defined by the number 1 ≤ cli ≤ 100 — the number of used chains. Next cli lines include couples of integers coi, j and cci, j, 1 ≤ coi, jM, 1 ≤ cci, j ≤ 109. The couples of integers and their quantity are in the separate lines.

The integer L, 1 ≤ L ≤ 100 is in the next line — the number of experiments. The next lines include their descriptions. Each experiment is defined by the integer 1 ≤ eli ≤ 100 — the number of used compound operations. In the next eli lines there are integers eoi, j and eci, j, 1 ≤ eoi, jK, 1 ≤ eci, j ≤ 109. The couples of numbers and their quantity are in separate lines.

Output

Output N numbers in a separate line for each experiment — which number of adornment is situated in the slot i for all integers i within the interval [1... N].

Examples
Input
7
2
4 1 2 3 4
3 4 5 7
2
1
1 1
1
2 1
3
1
1 1
1
2 1
2
1 1
2 1
Output
4 1 2 3 5 6 7 
1 2 3 7 4 6 5 
4 1 2 7 3 6 5
I. Polycarp and Heat Exchangers
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp does experiments again. He has N triangle heat exchangers on the field. Each i-th heat exchanger has input and output and their coefficients kini and kouti respectively. If two heat exchangers intersect (or first one touches second one), then thir inputs becamee molten together and their input coefficient became k, where , k1 and k2 are input coefficients of heat exchangers. Each point of field emits heat, heat comes out with specific speed. If this point is beneath some heat exchangers, it's value is multiplied by final value of their input coefficient and then it's multiplied by their output coefficients. Square of field with sides's length 1 emits 1 unit of heat. Polycarp wants to know value of heat per second, which emits all heat exchangers.

Input

The first line contains N, 1 ≤ N ≤ 10. N lines follow, each containing x1i, y1i, x2i, y2i, x3i, y3i, kini, kouti — coordinates of vertexes i-th heat exchanger, input and output coefficients. All numbers are separated by space, coordinates are integers, which are lesser than 101 and greater than  - 101, 0.1 ≤ kini, kouti ≤ 2.0. Triangles are not degenerate.

Output

Output summary value of heat per second, which emits all heat exchangers. You may assume that answers is coparated with the precision of 10 - 4.

Examples
Input
2
0 0 4 4 8 0 1 1
1 3 7 3 4 -1 1 1
Output
9.51785700
Input
2
-100 100 -100 -100 75 -100 0.5 2
100 100 100 -100 -75 -100 0.5 2
Output
17500.00000000
J. Polycarp and Dividend
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp have free time, collection of N decimal digits c1, ... , cN and positive integer A. He wants to find positive integer B, such that A divides B and B contains only digits from collection c1, ... , cN. Each digit from collection can be used any times. It is not required to use all the digits.

Input

The first line contains N — the number of digits in collection, 1 ≤ N ≤ 10. The second line contains N integer numbers ci (0 ≤ ci ≤ 9). Each digit can be there at most one time. The third line contains integer A, 1 ≤ A ≤ 105.

Output

Output B. If you cannot find it, then output -1.

Examples
Input
3
3 5 7
123
Output
5535
Input
1
1
1230
Output
-1
K. Polycarp and Lamps
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp continues to play with lamps. Today he illuminates cylinder with N lamps. Center of cylinder's bottom in (xc, yc, 0), height is h, radius is r. Bottom belongs to xOy plane, top is parallel to bottom and its center is (xc, yc, h). Polycarp prepares N lamps, i-th lamp situates in (xi, yi, zi) point. The size of lamps is enough small to neglect it. Lamps enough powerfull to lighten any point in the space, if there are no obstacles. Cylinder absolutely opaque. Polycarp wants to find illuminated area of cylinder.

Input

The first line contains four integer numbers: xc, yc, h, r, where xc, yc are coordinates of bottom's center, h is height and r is radius. The second line contains one integer number: N. Next N lines contains three integers: xi, yi, zi, these are coordinates of i-th lamp.

All coordinates are greater than  - 1001 and less than 1001. 1 ≤ h, r ≤ 1000. 1 ≤ N ≤ 100. There are no lamps in the cylinder and no lamps on cylinder's sides. In one point can be only one lamp.

Output

Output the square of illuminated area of cylinder. You may assume that answers is coparated with the precision of 10 - 6.

Examples
Input
0 0 10 10
1
0 0 100
Output
314.15926536
Input
0 0 10 10
4
-100 0 -100
0 -100 -25
100 0 25
0 100 100
Output
1256.63706144
Note

A Lamp illuminates bottom only if its z coordinate less than 0, and top if greats h. If a lamp in the plane of bottom it does not illuminate them, same situation with top.

L. Polycarp and Permutations
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Polycarp has set of integers 1, ..., N and parameters M и K. Polycarp is interested in number of permutations {ai} from numbers 1, ..., N, so that every permutation have exactly M inversions and K numbers are in their own place. Inversion is the pair of numbers i, j, so that ai > aj и i < j. Number i is postioned in it's own place if ai = i.

Input

Single line contains three integers N, M, K. 1 ≤ N ≤ 14, , 0 ≤ K ≤ N.

Output

One integer — number or permutations.

Examples
Input
4 0 4
Output
1
Input
12 7 3
Output
3000
Input
12 25 0
Output
3612516
Input
12 66 0
Output
1