Problem Statement

You are very absorbed in a famous role-playing game (RPG), "Everlasting -Zero-". An RPG is a game in which players assume the roles of characters in a fictional setting. While you play the game, you can forget your "real life" and become a different person.

To play the game more effectively, you have to understand two notions, a skill point and a special command. A character can boost up by accumulating his experience points. When a character boosts up, he can gain skill points.

You can arbitrarily allocate the skill points to the character's skills to enhance the character's abilities. If skill points of each skill meets some conditions simultaneously (e.g., the skill points of some skills are are greater than or equal to the threshold values and those of others are less than or equal to the values) , the character learns a special command. One important thing is that once a character learned the command, he will never forget it. And once skill points are allocated to the character, you cannot revoke the allocation. In addition, the initial values of each skill is 0.

The system is so complicated that it is difficult for ordinary players to know whether a character can learn all the special commands or not. Luckily, in the "real" world, you are a great programmer, so you decided to write a program to tell whether a character can learn all the special commnads or not. If it turns out to be feasible, you will be more absorbed in the game and become happy.

---

Input

The input is formatted as follows.

M N
K_1
s_{1,1} cond_{1,1} t_{1,1}
s_{1,2} cond_{1,2} t_{1,2}
...
s_{1,K_1} cond_{1,K_1} t_{1,K_1}
K_2
...
K_M
s_{M,1} cond_{M,1} t_{M,1}
s_{M,2} cond_{M,2} t_{M,2}
...
s_{M,K_M} cond_{M,K_M} t_{M,K_M}

The first line of the input contains two integers (M, N), where M is the number of special commands (1 \leq M \leq 100), N is the number of skills (1 \leq N \leq 100). All special commands and skills are numbered from 1.

Then M set of conditions follows. The first line of a condition set contains a single integer K_i (0 \leq K_i \leq 100), where K_i is the number of conditions to learn the i-th command. The following K_i lines describe the conditions on the skill values. s_{i,j} is an integer to identify the skill required to learn the command. cond_{i,j} is given by string "<=" or ">=". If cond_{i,j} is "<=", the skill point of s_{i,j}-th skill must be less than or equal to the threshold value t_{i,j} (0 \leq t_{i,j} \leq 100). Otherwise, i.e. if cond_{i,j} is ">=", the skill point of s_{i,j} must be greater than or equal to t_{i,j}.

Output

Output "Yes" (without quotes) if a character can learn all the special commands in given conditions, otherwise "No" (without quotes).

Sample Input 1

2 2
2 
1 >= 3
2 <= 5
2
1 >= 4
2 >= 3

Output for the Sample Input 1

Yes

Sample Input 2

2 2
2 
1 >= 5
2 >= 5
2
1 <= 4
2 <= 3

Output for the Sample Input 2

Yes

Sample Input 3

2 2
2 
1 >= 3
2 <= 3
2
1 <= 2
2 >= 5

Output for the Sample Input 3

No

Sample Input 4

1 2
2
1 <= 10
1 >= 15

Output for the Sample Input 4

No

Sample Input 5

5 5
3
2 <= 1
3 <= 1
4 <= 1
4
2 >= 2
3 <= 1
4 <= 1
5 <= 1
3
3 >= 2
4 <= 1
5 <= 1
2
4 >= 2
5 <= 1
1
5 >= 2 

Output for the Sample Input 5

Yes

Problem Statement

Given an integer interval \[A, B\] and an integer C, your job is to calculate the number of occurrences of C as string in the interval.

For example, 33 appears in 333 twice, and appears in 334 once. Thus the number of occurrences of 33 in \[333, 334\] is 3.

---

Input

The test case is given by a line with the three integers, A, B, C (0 \leq A \leq B \leq 10^{10000}, 0 \leq C \leq 10^{500}).

Output

Print the number of occurrences of C mod 1000000007.

Sample Input 1

1 3 2

Output for Sample Input 1

1

Sample Input 2

333 334 33

Output for Sample Input 2

3

Sample Input 3

0 10 0

Output for Sample Input 3

2

Problem Statement

Three animals Frog, Kappa (Water Imp) and Weasel are playing a card game.

In this game, players make use of three kinds of items: a guillotine, twelve noble cards and six action cards. Some integer value is written on the face of each noble card and each action card. Before stating the game, players put twelve noble cards in a line on the table and put the guillotine on the right of the noble cards. And then each player are dealt two action cards. Here, all the noble cards and action cards are opened, so the players share all the information in this game.

Next, the game begins. Each player takes turns in turn. Frog takes the first turn, Kappa takes the second turn, Weasel takes the third turn, and Frog takes the fourth turn, etc. Each turn consists of two phases: action phase and execution phase in this order.

In action phase, if a player has action cards, he may use one of them. When he uses an action card with value on the face y, y-th (1-based) noble card from the front of the guillotine on the table is moved to in front of the guillotine, if there are at least y noble cards on the table. If there are less than y cards, nothing happens. After the player uses the action card, he must discard it from his hand.

In execution phase, a player just remove a noble card in front of the guillotine. And then the player scores x points, where x is the value of the removed noble card.

The game ends when all the noble cards are removed.

Each player follows the following strategy:

• Each player assume that other players would follow a strategy such that their final score is maximized.
• Actually, Frog and Weasel follows such strategy.
• However, Kappa does not. Kappa plays so that Frog's final score is minimized.
• Kappa knows that Frog and Weasel would play under ``wrong'' assumption: They think that Kappa would maximize his score.
• As a tie-breaker of multiple optimum choises for each strategy, assume that players prefer to keep as many action cards as possible at the end of the turn.
• If there are still multiple optimum choises, players prefer to maximuze the total value of remaining action cards.

Your task in this problem is to calculate the final score of each player.

---

Input

The input is formatted as follows.

x_{12} x_{11} x_{10} x_9 x_8 x_7 x_6 x_5 x_4 x_3 x_2 x_1
y_1 y_2
y_3 y_4
y_5 y_6

The first line of the input contains twelve integers x_{12}, x_{11}, …, x_{1} (-2 \leq x_i \leq 5). x_i is integer written on i-th noble card from the guillotine. Following three lines contains six integers y_1, …, y_6 (1 \leq y_j \leq 4). y_1, y_2 are values on Frog's action cards, y_3, y_4 are those on Kappa's action cards, and y_5, y_6 are those on Weasel's action cards.

Output

Print three space-separated integers: the final scores of Frog, Kappa and Weasel.

Sample Input 1

3 2 1 3 2 1 3 2 1 3 2 1
1 1
1 1
1 1

Output for the Sample Input 1

4 8 12

Sample Input 2

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

Output for the Sample Input 2

8 10 12

Sample Input 3

0 0 0 0 0 0 0 -2 0 -2 5 0
1 1
4 1
1 1

Output for the Sample Input 3

-2 -2 5

Problem Statement

The government has declared a state of emergency due to the MOFU syndrome epidemic in your country. Persons in the country suffer from MOFU syndrome and cannot get out of bed in the morning. You are a programmer working for the Department of Health. You have to take prompt measures.

The country consists of n islands numbered from 1 to n and there are ocean liners between some pair of islands. The Department of Health decided to establish the quarantine stations in some islands and restrict an infected person's moves to prevent the expansion of the epidemic. To carry out this plan, there must not be any liner such that there is no quarantine station in both the source and the destination of the liner. The problem is the department can build at most K quarantine stations due to the lack of budget.

Your task is to calculate whether this objective is possible or not. And if it is possible, you must calculate the minimum required number of quarantine stations.

---

Input

The test case starts with a line containing three integers N (2 \leq N \leq 3{,}000), M (1 \leq M \leq 30{,}000) and K (1 \leq K \leq 32). Each line in the next M lines contains two integers a_i (1 \leq a_i \leq N) and b_i (1 \leq b_i \leq N). This represents i-th ocean liner connects island a_i and b_i. You may assume a_i \neq b_i for all i, and there are at most one ocean liner between all the pairs of islands.

Output

If there is no way to build quarantine stations that satisfies the objective, print "Impossible" (without quotes). Otherwise, print the minimum required number of quarantine stations.

Sample Input 1

3 3 2
1 2
2 3
3 1

Output for the Sample Input 1

2

Sample Input 2

3 3 1
1 2
2 3
3 1

Output for the Sample Input 2

Impossible

Sample Input 3

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

Output for the Sample Input 3

4

Sample Input 4

10 10 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Output for the Sample Input 4

4

Problem Statement

You are given an undirected weighted graph G with n nodes and m edges. Each edge is numbered from 1 to m.

Let G_i be an graph that is made by erasing i-th edge from G. Your task is to compute the cost of minimum spanning tree in G_i for each i.

---

Input

The dataset is formatted as follows.

n m
a_1 b_1 w_1
...
a_m b_m w_m

The first line of the input contains two integers n (2 \leq n \leq 100{,}000) and m (1 \leq m \leq 200{,}000). n is the number of nodes and m is the number of edges in the graph. Then m lines follow, each of which contains a_i (1 \leq a_i \leq n), b_i (1 \leq b_i \leq n) and w_i (0 \leq w_i \leq 1{,}000{,}000). This means that there is an edge between node a_i and node b_i and its cost is w_i. It is guaranteed that the given graph is simple: That is, for any pair of nodes, there is at most one edge that connects them, and a_i \neq b_i for all i.

Output

Print the cost of minimum spanning tree in G_i for each i, in m line. If there is no spanning trees in G_i, print "-1" (quotes for clarity) instead.

Sample Input 1

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

Output for the Sample Input 1

8
6
7
10
6
6

Sample Input 2

4 4
1 2 1
1 3 10
2 3 100
3 4 1000

Output for the Sample Input 2

1110
1101
1011
-1

Sample Input 3

7 10
1 2 1
1 3 2
2 3 3
2 4 4
2 5 5
3 6 6
3 7 7
4 5 8
5 6 9
6 7 10

Output for the Sample Input 3

27
26
25
29
28
28
28
25
25
25

Sample Input 4

3 1
1 3 999

Output for the Sample Input 4

-1

Problem Statement

You work for invention center as a part time programmer. This center researches movement of protein molecules. It needs how molecules make clusters, so it will calculate distance of all pair molecules and will make a histogram. Molecules’ positions are given by a N x N grid map. Value C_{xy} of cell (x, y) in a grid map means that C_{xy} molecules are in the position (x, y).

You are given a grid map, please calculate histogram of all pair molecules.

---

Input

Input is formatted as follows.

N
C_{11} C_{12} ... C_{1N}
C_{21} C_{22} ... C_{2N}
...
C_{N1} C_{N2} ... C_{NN}

First line contains the grid map size N (1 \leq N \leq 1024). Each next N line contains N numbers. Each numbers C_{xy} (0 \leq C_{xy} \leq 9) means the number of molecule in position (x,y). There are at least 2 molecules.

Output

Output is formatted as follows.

D_{ave}
d_{1} c_{1}
d_{2} c_{2}
...
d_{m} c_{m}

Print D_{ave} which an average distance of all pair molecules on first line. Next, print histogram of all pair distance. Each line contains a distance d_i and the number of pair molecules c_i(0 \lt c_i). The distance d_i should be calculated by squared Euclidean distance and sorted as increasing order. If the number of different distance is more than 10,000, please show the first 10,000 lines. The answer may be printed with an arbitrary number of decimal digits, but may not contain an absolute or relative error greater than or equal to 10^{-8}.

Sample Input 1

2
1 0
0 1

Output for the Sample Input 1

1.4142135624
2 1

Sample Input 2

3
1 1 1
1 1 1
1 1 1

Output for the Sample Input 2

1.6349751825
1 12
2 8
4 6
5 8
8 2

Sample Input 3

5
0 1 2 3 4
5 6 7 8 9
1 2 3 2 1
0 0 0 0 0
0 0 0 0 1

Output for the Sample Input 3

1.8589994382
0 125
1 379
2 232
4 186
5 200
8 27
9 111
10 98
13 21
16 50
17 37
18 6
20 7
25 6

Problem Statement

Flora is a freelance carrier pigeon. Since she is an excellent pigeon, there are too much task requests to her. It is impossible to do all tasks, so she decided to outsource some tasks to Industrial Carrier Pigeon Company.

There are N cities numbered from 0 to N-1. The task she wants to outsource is carrying f freight units from city s to city t. There are M pigeons in the company. The i-th pigeon carries freight from city s_i to t_i, and carrying cost of u units is u a_i if u is smaller than or equals to d_i, otherwise d_i a_i + (u-d_i)b_i. Note that i-th pigeon cannot carry from city t_i to s_i. Each pigeon can carry any amount of freights. If the pigeon carried freight multiple times, the cost is calculated from total amount of freight units he/she carried.

Flora wants to minimize the total costs. Please calculate minimum cost for her.

---

Input

The test case starts with a line containing five integers N (2 \leq N \leq 100), M (1 \leq M \leq 1{,}000), s (0 \leq s \leq N-1), t (0 \leq t \leq N-1) and f (1 \leq f \leq 200). You may assume s \neq t. Each of the next M lines contains five integers s_i (0 \leq s_i \leq N-1), t_i (0 \leq t_i \leq N-1), a_i (0 \leq a_i \leq 1{,}000), b_i (0 \leq b_i \leq 1{,}000) and d_i (1 \leq d_i \leq 200). Each denotes i-th pigeon's information. You may assume at most one pair of a_i and b_i satisfies a_i < b_i, all others satisfies a_i > b_i.

Output

Print the minimum cost to carry f freight units from city s to city t in a line. If it is impossible to carry, print "Impossible" (quotes for clarity).

Sample Input 1

2 2 0 1 5
0 1 3 0 3
0 1 2 1 6

Output for the Sample Input 1

9

Sample Input 2

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

Output for the Sample Input 2

18

Sample Input 3

2 1 0 1 1
1 0 1 0 1

Output for the Sample Input 3

Impossible

Sample Input 4

2 2 0 1 2
0 1 5 1 2
0 1 6 3 1

Output for the Sample Input 4

9

Sample Input 5

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

Output for the Sample Input 5

14

Problem Statement

There are two circles with radius 1 in 3D space. Please check two circles are connected as chained rings.

---

Input

The input is formatted as follows.

{c_x}_1 {c_y}_1 {c_z}_1
{v_x}_{1,1} {v_y}_{1,1} {v_z}_{1,1} {v_x}_{1,2} {v_y}_{1,2} {v_z}_{1,2}
{c_x}_2 {c_y}_2 {c_z}_2
{v_x}_{2,1} {v_y}_{2,1} {v_z}_{2,1} {v_x}_{2,2} {v_y}_{2,2} {v_z}_{2,2}

First line contains three real numbers(-3 \leq {c_x}_i, {c_y}_i, {c_z}_i \leq 3). It shows a circle's center position. Second line contains six real numbers(-1 \leq {v_x}_{i,j}, {v_y}_{i,j}, {v_z}_{i,j} \leq 1). A unit vector ({v_x}_{1,1}, {v_y}_{1,1}, {v_z}_{1,1}) is directed to the circumference of the circle from center of the circle. The other unit vector ({v_x}_{1,2}, {v_y}_{1,2}, {v_z}_{1,2}) is also directed to the circumference of the circle from center of the circle. These two vectors are orthogonalized. Third and fourth lines show the other circle information in the same way of first and second lines. There are no cases that two circles touch.

Output

If two circles are connected as chained rings, you should print "YES". The other case, you should print "NO". (quotes for clarity)

Sample Input 1

0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
1.0 0.0 0.5
1.0 0.0 0.0 0.0 0.0 1.0

Output for the Sample Input 1

YES

Sample Input 2

0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
0.0 3.0 0.0
0.0 1.0 0.0 -1.0 0.0 0.0

Output for the Sample Input 2

NO

Sample Input 3

1.2 2.3 -0.5
1.0 0.0 0.0 0.0 1.0 0.0
1.1 2.3 -0.4
1.0 0.0 0.0 0.0 0.70710678 0.70710678

Output for the Sample Input 3

YES

Sample Input 4

1.2 2.3 -0.5
1.0 0.0 0.0 0.0 1.0 0.0
1.1 2.7 -0.1
1.0 0.0 0.0 0.0 0.70710678 0.70710678

Output for the Sample Input 4

NO

Problem Statement

You are given N empty arrays, t_1, ..., t_n. At first, you execute M queries as follows.

• add a value v to array t_i (a \leq i \leq b)

Next, you process Q following output queries.

• output the j-th number of the sequence sorted all values in t_i (x \leq i \leq y)

---

Input

The dataset is formatted as follows.

N M Q
a_1 b_1 v_1
...
a_M b_M v_M
x_1 y_1 j_1
...
x_Q y_Q j_Q

The first line contains three integers N (1 \leq N \leq 10^9), M (1 \leq M \leq 10^5) and Q (1 \leq Q \leq 10^5). Each of the following M lines consists of three integers a_i, b_i and v_i (1 \leq a_i \leq b_i \leq N, 1 \leq v_i \leq 10^9). Finally the following Q lines give the list of output queries, each of these lines consists of three integers x_i, y_i and j_i (1 \leq x_i \leq y_i \leq N, 1 \leq j_i \leq Σ_{x_i \leq k \leq y_i} |t_k|).

Output

For each output query, print in a line the j-th number.

Sample Input 1

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

Output for the Sample Input 1

2

After the M-th query is executed, each t_i is as follows:

[1,3], [1], [1,2], [1,1,2], [1,1]

The sequence sorted values in t_1, t_2 and t_3 is [1,1,1,2,3]. In the sequence, the 4-th number is 2.

Sample Input 2

10 4 4
1 4 11
2 3 22
6 9 33
8 9 44
1 1 1
4 5 1
4 6 2
1 10 12

Output for the Sample Input 2

11
11
33
44

Problem Statement

You have a directed graph. Some non-negative value is assigned on each edge of the graph. You know that the value of the graph satisfies the flow conservation law That is, for every node v, the sum of values on edges incoming to v equals to the sum of values of edges outgoing from v. For example, the following directed graph satisfies the flow conservation law.

Suppose that you choose a subset of edges in the graph, denoted by E', and then you erase all the values on edges other than E'. Now you want to recover the erased values by seeing only remaining information. Due to the flow conservation law, it may be possible to recover all the erased values. Your task is to calculate the smallest possible size for such E'.

For example, the smallest subset E' for the above graph will be green edges in the following figure. By the flow conservation law, we can recover values on gray edges.

---

Input

The input consists of multiple test cases. The format of each test case is as follows.

N M
s_1 t_1
...
s_M t_M

The first line contains two integers N (1 \leq N \leq 500) and M (0 \leq M \leq 3,000) that indicate the number of nodes and edges, respectively. Each of the following M lines consists of two integers s_i and t_i (1 \leq s_i, t_i \leq N). This means that there is an edge from s_i to t_i in the graph.

You may assume that the given graph is simple:

• There are no self-loops: s_i \neq t_i.
• There are no multi-edges: for all i < j, \{s_i, t_i\} \neq \{s_j, t_j\}.

Also, it is guaranteed that each component of the given graph is strongly connected. That is, for every pair of nodes v and u, if there exist a path from v to u, then there exists a path from u to v.

Note that you are NOT given information of values on edges because it does not effect the answer.

Output

For each test case, print an answer in one line.

Sample Input 1

9 13
1 2
1 3
2 9
3 4
3 5
3 6
4 9
5 7
6 7
6 8
7 9
8 9
9 1

Output for the Sample Input 1

5

Sample Input 2

7 9
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
7 1

Output for the Sample Input 2

3

Sample Input 3

4 4
1 2
2 1
3 4
4 3

Output for the Sample Input 3

2