2015, VIII Samara Regional Intercollegiate Programming Contest
A. Did he drop any good loot?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Slava plays a very cool RPG. He has just cleaned up the dungeon, and n cool artifacts have been dropped down. He wants to sell them to gain as much profit as he can. Each artifact has its own price pi and weight wi. Slava cannot carry artifacts with the total weight greater than m, but it's possible to activate some of them. Being activated, the i-th artifact increases Slava's strength and adds additional weight di to Slava's weight limit. Activated artifacts don't disappear, their price and weight don't change and they still can be sold. Slava can activate no more than 2 artifacts at the same time.

More formally, Slava wants to choose a set of artifacts with the greatest total price among all correct sets. The set of artifacts i1, i2, ..., ik (k ≤ n) is called correct if wi1 + wi2 + ... + wik ≤ m + s, where s is the additional weight limit gained from the actifacts activation: s = dj1 + dj2, if Slava activated artifacts j1 and j2 (j1 ≠ j2), s = dj — if he activated only artifact j, and s = 0, if he didn't activate any artifacts (j1, j2 and j must be contained in the set of chosen artifacts i1, i2, ..., ik).

Input

The first line contains two space-separated integers n and m (1 ≤ n ≤ 104, 1 ≤ m ≤ 500) — the number of artifacts and the Slava's weight limit.

Each of the next n lines contains three space-separated integers pi, wi and di (1 ≤ pi ≤ 105, 1 ≤ wi ≤ 100, 0 ≤ di ≤ 100) — the price of the i-th artifact, its weight and the additional weight limit it gains at its activation.

Output

Write one integer — the maximum total price of the artifacts Slava can take with him.

Examples
Input
5 10
1 5 3
2 4 0
3 2 2
4 1 4
5 3 1
Output
15
Input
3 10
100 100 20
200 80 30
300 60 40
Output
0
Note

In the first sample Slava cannot just take all artifacts — his weight limit is 10, and the total weight of all artifacts is 15. That's why he activates artifacts 1 and 4, which leads to increasing his weight limit to 10 + 3 + 4 = 17 (in fact, he can activate any pair of artifacts which increases his weight limit by 5 or more).

In the second sample Slava cannot take any artifacts, either with the activation or without it.

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

Pavel loves Far Manager very much. By default, Far shows files in a certain number of columns each of which holds p files. Besides, there is also a «zero file» — the link to the parent directory, after which the files in the current directory are shown.

Pavel is viewing a directory with n files numbered from 1 to n. He needs to select the file x. To do that, he has to place the cursor onto this file. He can press any of the four arrow keys: up / down arrows move the cursor by 1 file, and left / right arrows move it by p files (or place the cursor onto the «zero file» or the last file if less than p files remains in the cursor's movement direction).

Your task is to help Pavel to determine the minimum number of key presses to select the file x. At the beginning the cursor points to the link to the parent directory.

Input

The only line contains 3 integers p, n and x (1 ≤ p ≤ 109, 1 ≤ n ≤ 109, 1 ≤ x ≤ n) — the maximum number of files in a column, the total number of files in the directory viewed by Pavel and the file he wants to select.

Output

Write one integer — the minimum number of key presses Pavel needs to select the file x.

Examples
Input
5 8 3
Output
3
Input
6 20 14
Output
4
Input
8 33 33
Output
5
C. Modern Art
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sergey is a modern artist who uses 3D printer in his works. He has just come up with the idea of his next work. He is going to print n colored bars and place them horizontally one over another (the bars can be considered as horizontal segments on the plane, which have positive lengths and belong to pairwise distinct lines parallel to X-axis), but he also wants to satisfy some conditions (he is an artist, after all). There are two types of conditions: precendence (type A) and intersection (type B).

If there is a precendence condition between two bars i and j, the bar i must be placed strictly to the left of the bar j (that is, X-coordinate of any point of bar i must be strictly less than X-coordinate of any point of bar j).

Intersection condition between bars i and j means that both bars must have at least one point which is not an end such that the X-coordinates of these points are equal.

If there are no conditions between some two bars, they can be placed in any order relatively to each other.

Help Sergey to find perfect X-coordinates for his bars or say that it's impossible. If his work is successful he might even share his earnings with you!

Input

The first line contains three space-separated integers n, a and b (1 ≤ n ≤ 105, 0 ≤ a, b ≤ 105) — the number of bars and the numbers of conditions of type A and type B.

Each of the next a lines contains two space-separated integers fa[i] and sa[i] (1 ≤ fa[i], sa[i] ≤ n, fa[i] ≠ sa[i]) — the indices of bars for which the condition of type A must be satisfied.

Each of the next b lines contains two space-separated integers fb[i] and sb[i] (1 ≤ fb[i], sb[i] ≤ n, fb[i] ≠ sb[i]) — the indices of bars for which the condition of type B must be satisfied.

Output

If the required arrangement of bars doesn't exist, write «NO» (without quotes).

Otherwise in the first line write «YES» (without quotes). Next, write n lines, the i-th of which should contain two integers li and ri (0 ≤ li < ri ≤ 109) — the X-coordinates of the left and right ends of the i-th bar.

Examples
Input
4 2 1
1 2
2 3
3 4
Output
YES
0 1
2 3
4 6
5 7
Input
3 2 0
1 2
2 1
Output
NO
D. Unfair Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The game with abstract n-faced dice is described by the following rules. The inventory used in the game is a certain number of abstract n-faced dice, each of their faces has its own integer number, such that all numbers on all faces are distinct. Two players take part in the game. At the beginning the first player chooses his dice. After that, the second player, knowing the first player's choice, chooses his dice (of course, he can't choose the first player's dice). Then players throw their dice simultaneously, and the player with the bigger number on his dice wins.

Constantine wants to play an infinite number of games against Mike. For this purpose, he needs to create three n-faced dice having the following properties: whichever dice is chosen by the first player, the second player always can choose his dice in such a way that the probability of his victory is strictly greater than . Constantine is planning to give Mike the first move: being the second player, he will win more frequently by choosing the right dice, and will earn an infinite amount of money.

Mike has agreed with these conditions, but the choice of number of faces n is after him. Help Constantine to create the needed set of n-faced dice.

Input

The only line contains one integer n (1 ≤ n ≤ 1000) — the number of faces of the dice.

Output

If the required set of abstract n-faced dice doesn't exist, output «FAIL».

Otherwise in the first line output «WIN», and in each of the next three lines output n integers — the numbers on the faces of the corresponding dice. All 3n numbers must be distinct and belong to the interval from 1 to 3n. If there are many possible solutions, output any of them.

Examples
Input
1
Output
FAIL
Input
5
Output
WIN
1 3 7 14 15
2 6 10 11 13
4 5 8 9 12
Input
6
Output
WIN
4 6 8 9 11 18
2 3 7 13 15 17
1 5 10 12 14 16
E. SuperHyperMarket
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The day of opening of the greatest shop in the world is coming. To show the full potential of their shop, in particular, the unbelievable speed of the cash desks, the owners of the shop came up with the following move: n most average customers will be let into the shop, and the cash desks will be opened only after all customers will choose their purchases and take their places in the queues. The problem is that if the customers walk along the cash desks and choose the optimal queue, the process can last for several hours. That's why you are asked to choose queues for all customers automatically.

The sociologists told you how the average customers choose the queue: they look at the number of people in the queue and at the number of the purchases of the last two people in it. Formally, the customer chooses the cash desk i for which the value xi = ci·p is minimal. Here, ci is the number of people in the i-th queue, and p — is the average (by the average customer's definition) number of purchases of one person in the queue. The value of p is calculated by two last people in the queue: p = (p1 + p2) / 2, if there are two or more people in the queue (p1 and p2 are the numbers of purchases of the last two people), p = p1, if there is only one customer in the queue, and p = 0 if the queue is empty. If there are several cash desks with minimal xi, the customer chooses the one with the minimal number i.

After the customers choose their queue, they don't go anywhere out of it.

Input

The first line contains two space-separated integers n and k (1 ≤ n, k ≤ 105) — the number of customers and the number of cash desks in the shop.

The next line contains n space-separated integers pj (1 ≤ pj ≤ 1000) — the numbers of purchases of the j-th customer in the chronological order. Every customer chooses his queue before the next customer starts doing it.

Output

Write n space-separated integers in one line. The i-th number should be equal to the number of cash desk where the i-th customer will go using the criterion described in the problem.

Examples
Input
5 2
1 3 1 2 3
Output
1 2 1 1 2
Input
5 7
1 3 1 2 3
Output
1 2 3 4 5
F. The Berland Championship
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Every year BerSU (Berland State University) holds the programming contest «The Berland Championship». This year Andrey, the student of BSAU (Berland State Alternative University), helped to prepare the problems. There were m problems prepared in total.

Andrey is proud of his university very much so he wants the BSAU team to win. Of course, he isn't allowed to share the problems with BSAU teams, but he can give advice how to form the teams.

n BSAU students want to take part in the competition. For each student, Andrey knows what problems he can solve, and also what is his productivity — the maximum number of problems he can solve during the contest. Every team must consist of three students. Andrey believes that BSAU students will act optimally at the contest, that is, everyone will solve the maximal number of problems he can. However, no student will solve more problems than his productivity, and no team will solve problems that aren't solvable by its students.

Help Andrey to form exactly one team of three students so it could solve the maximal number of problems comparing to all other possible BSAU teams.

Input

The first line contains two integers n, m (3 ≤ n ≤ 50, 1 ≤ m ≤ 1000) — the number of BSAU students and the number of problems.

The second line contains n integers pi (0 ≤ pi ≤ m) — the productivities of the students.

Each of the next n lines contains a string of uppercase and lowercase Latin letters namei (|namei| ≤ 10) — the name of the i-th student. All names are pairwise distinct.

Then the binary matrix a of size n × m follows. Its rows correspond to students, and columns — to problems. If ai, j is 1, i-th student can solve j-th problem, otherwise he can't.

Output

In the first line output a single integer s — the maximal number of problems the team formed by Andrey can solve.

In the second line output the names of the students in this team. The names can be written in any order.

If there are several optimal solutions, output any of them.

Examples
Input
5 5
3 2 2 3 1
Slava
Andrew
Egor
Denis
Sergey
11011
10100
00001
00100
10000
Output
5
Slava Andrew Egor
Input
4 6
1 2 1 2
Denis
Andrew
Egor
Slava
100011
111100
000101
000111
Output
5
Denis Andrew Slava
G. The Lost Graph
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Student Vladislav is taking programming exam. He hasn't prepared properly and had a bad luck to get a question about some complicated graph algorithm that will be definitely useless for him for the rest of his life. He quickly asked his groupmate a cheatsheet and discovered the following pseudocode there:


function dfs(v)
begin
    visited[v] := true
    print("in " + v)
    for k := 1 : n do
    begin
        if adjacent(v, k) and not visited[k] do
        begin
            dfs(k)
        end
    end
    print("out " + v)
end

Vladislav manually executed the algorithm on the connected undirected graph just drawn by him. Unfortunately, he was very nervous and ate the piece of paper where this graph was drawn, but he has to show the graph to his teacher. Help Vladislav to restore the graph. It must be done as soon as possible, so the restored graph should contain the minimal possible number of edges.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of vertices in the graph.

It's followed by the execution result of the algorithm completely useless for Vladislav. It consists of 2n lines «in x» or «out x» where x is the number of vertex (1 ≤ x ≤ n).

It's guaranteed that all vertices from 1 to n exist in the graph, and that the input really specifies the execution result of the algorithm on some existing graph.

Output

Output (n - 1) lines, two numbers on each line — the numbers of vertices connected by edges. You can output the pairs of vertices and the vertices in pairs in any order.

Examples
Input
2
in 1
in 2
out 2
out 1
Output
1 2
Input
4
in 4
in 2
out 2
in 3
in 1
out 1
out 3
out 4
Output
1 3
2 4
3 4
H. Noisy Lecture
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Teacher N/A is delivering a lecture. The lecture consists of n sentences and goes this way: each sentence should be firstly remembered by the teacher from her copy-book (remembering the i-th sentence takes ai time) and then written on the blackboard (it takes bi time). If there is a noise in the lecture hall, N/A gets distracted: if she is remembering the sentence at this moment, she forgots it and will have to remember it from the beginning after the noise ends. And if she is writing the sentence on the blackboard, she will have to remember the remaining part of the sentence (she has to spend the corresponding part of ai for that) and write that part on the blackboard.

There are k students in the lecture hall. Each of these students can initiate the noise of duration cj exactly once. What is the maximal amount of time students can slow down the lecture?

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of sentences in the lecture.

The second line contains n space-separated integers ai (1 ≤ ai ≤ 1000) — how much time it takes to remember the i-th sentence.

The third line contains n space-separated integers bi (1 ≤ bi ≤ 1000) — how much time it takes to write the i-th sentence on the blackboard.

The fourth line contains a single integer k (1 ≤ k ≤ 1000) — the number of students in the lecture hall.

The fifth line contains k space-separated integers cj (1 ≤ cj ≤ 1000) — the duration of noise which can be initiated by the j-th student.

Output

Output one integer — the maximal amount of time for which the lecture can be slowed down.

Examples
Input
3
3 2 1
1 5 3
2
1 2
Output
9
Input
4
2 1 2 1
1 2 3 4
3
2 3 1
Output
12
I. Goat in the Field
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Goat Tanya accidentally got out of the garden and found herself in the field. The goat got confused since she haven't been here before so she decided to walk straight in the certain direction. The field consists of the infinite number of 1 × 1 cells, and each of these cells is connected with four other cells by their sides. In a single turn the goat moves to the adjacent cell in her movement direction.

Shepherds have noticed the disappearence and try to catch the goat. Every shepherd in his turn can move in any direction by one or two cells, but he can't change the direction during the turn. They also can just stand in their cells instead of moving. The goat is catched if some shepherd at the end of his turn is located in the goat's cell. At the beginning no shepherd is located in the same cell as the goat.

Tanya and shepherds move in rotation — the goat moves first, and then the shepherds move in the same order as in the input. Your task is to find which shepherd will be the first to catch the goat.

Input

The first line contains two integers x, y (|x|, |y| ≤ 1000) — the initial coordinates of the goat.

The second line contains a string s which determines the goat's movement direction. s can be one of the four following strings (the quotes are for clarity):

  • «LEFT» — the goat moves to the left, x coordinate decreases by 1,
  • «RIGHT» — the goat moves to the right, x coordinate increases by 1,
  • «UP» — the goat moves to the top, y coordinate increases by 1,
  • «DOWN» — the goat moves to the bottom, y coordinate decreases by 1.

The third line contains one integer n (1 ≤ n ≤ 1000) — the number of shepherds.

The i-th of the n following lines contains a string () of lowercase Latin letters, and two integers xi, yi (|xi|, |yi| ≤ 1000) — the name of the i-th shepherd and his initial coordinates. It's guaranteed that all names are distinct.

Output

Output a single string — the name of the shepherd which will catch the goat first.

Examples
Input
0 0
LEFT
3
andrew -10 0
denis 10 0
ilia 0 10
Output
andrew
Input
10 2
UP
3
danila 5 4
sashac 11 1
sashab 12 10
Output
sashac
Input
0 0
UP
2
mike 2 1
constantine 0 1
Output
mike
J. Ticket Booking
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The biggest student ACM (Anarchy Code Modification) contest will be held in N-sk city soon. Slava is the leader of the group of students who will take part in this competition, so he must buy the train tickets for all members of the group. Each student told him his favourite seat number where this student wants to travel (all numbers are distinct).

Ticket window workers have gone on strike, so Slava has to use the terminal. The process of buying tickets in the terminal goes this way:

  1. The personal data of the passengers is entered. The maximum number of people whose information can be entered at one terminal usage is k.
  2. The lower and upper bounds of the seat numbers are entered. This segment can contain the seats that have been already bought. First c free seats in this segment are booked, where c is the number of people whose information has been filled at the previous step. If the segment doesn't contain enough free seats, the booking isn't performed.

Every terminal usage is accompanied by the entering of the great amount of information, so Slava wants to minimize the number of usages. He can't determine the optimal order by himself — the last bus to his home is about to leave — so you should help him.

Input

The first line contains three space-separated integers n, m and k (1 ≤ n, m, k ≤ 105, n ≤ m) — the number of students in the group, the number of free seats and the maximal number of people at one terminal usage.

The second line contains n distinct integers wi (1 ≤ wi ≤ 109) — the seat number preferred by the i-th student. They are sorted in ascending order.

The third line contains m distinct integers fj (1 ≤ fj ≤ 109) — the numbers of free seats. They are also sorted in ascending order.

It's guaranteed that every student wants to travel at a free seat. That is, for each 1 ≤ i ≤ n there exists such 1 ≤ j ≤ m that wi = fj.

Output

In the first line write a single integer s — the minimal number of terminal usages.

In each of the next s lines write the information about terminal usages — the number of people and their numbers, separated by spaces. Each student should be presented in only one terminal usage. The tickets should be bought for all students in the group.

Examples
Input
4 6 2
1 4 5 6
1 2 4 5 6 8
Output
3
1 1 
2 2 3 
1 4
Input
12 21 4
2 6 8 10 12 28 40 44 46 48 50 52
2 4 6 8 10 12 24 26 28 30 32 33 34 35 36 40 44 46 48 50 52
Output
5
1 1 
4 2 3 4 5 
1 6 
4 7 8 9 10 
2 11 12
K. Team Rating
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alex and Kostya have created their own Codeforces. To draw attention, they decided to hold a contest called Jaguar Turnik Cup. As in VK Cup, only teams consisting of two people can take part, and Alex also banned the teams of only one person. The rating of each person was taken from Codeforces, and the only task remained is to calculate the rating of teams.

After many disputes it was decided to use the following formula: , where is the maximal personal rating in the team, and is the minimal one. Though, it was still unclear what coefficients x and y should be.

After some more disputes everyone agreed that these coefficients should safisfy the following conditions: x + y = 1, x, y ≥ 0. However, the exact values couldn't be chosen, so Alex and Kostya invited their friends to take part in the warm-up contest. There were n teams in total, each team consisted of two people, and the Codeforces rating of each person was known.

The contest has finished successfully, and the creators decided to choose such x and y that the teams in the standings would be sorted by their team rating in non-ascending order. Can they do that?

Input

The first line contains a single integer n (1 ≤ n ≤ 106) — the number of teams took part in the warm-up contest.

The i-th of the following n lines contains two integers ai, bi (1 ≤ ai, bi ≤ 10000) — the personal ratings of the first and the second members of the team on the i-th place.

Output

Write «YES» or «NO» (without quotes) — depending on if it's possible to choose the coefficients as described.

Examples
Input
3
2106 1946
1955 1859
1778 1669
Output
YES
Input
3
10 2
8 8
9 6
Output
NO
L. Hanoi Towers and the Progress
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Andrey doesn't like Hanoi — for hundreds of years the highest buildings there are three ancient towers, and every year giant rings are moved from one tower to another using the same algorithm (see Notes section). Every year Andrey suffers from the fact that a huge amount of money is spent on such weird amusement — really, why do they move these rings with the help of lots of cranes, blocking the city center for several days? But the progress moves forward, and in the next year k additional small towers will be built in Hanoi. These towers won't be able to hold more than one ring. Having read this, Andrey immediately became interested in the minimal number of turns required to move n rings between big towers after this innovation. He doesn't want to spend even a second on this city, so it's your task to do these calculations.

Input

The only line contains two space-separated integers n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ 109) — the number of rings and the number of additional towers (the total number of towers will be k + 3).

Output

Output the minimal number of turns to move all rings from one big tower to another. As this number can be too large, output its remainder of division by 109 + 7.

Examples
Input
3 0
Output
7
Input
3 1
Output
5
Input
42 0
Output
46480317
Input
1000 0
Output
688423209
Note

«Hanoi towers» is the puzzle with three rods («towers»). At the beginning there are some rings on one of these rods, all of them have different size, and the smaller rings lie higher. The task is to move all the rings to another rod. In one turn the player can move one ring from the top of one rod to the top of another rod, and it's prohibited to put the larger ring onto the smaller one.

M. The Fifth Season
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cersei and Jaime has stolen n gold coins from the Casterly Rock reserves. They decided to play a game while the disappearence is not detected.

The game consists of q rounds. At the beginning of each round all n coins lie in a heap. The players move in rotation, taking from the heap no less than ki and no more than li coins (ki ≤ li, i is the number of round). The player who can't do the move loses.

Cersei and Jaime have determined the pairs of numbers (ki, li) for each round of the game. They don't see any point in finding out who wins in what round as they choose who moves the first by flipping a coin. They are interested in the maximal length of each round, provided that they play optimally (intend to win). The length of the round is the total number of moves made by both Cersei and Jaime.

Your task is to find the maximal possible length of each round of the game.

Input

The first line contains two integers n and q — the number of coins and the number of rounds (1 ≤ n ≤ 106, 1 ≤ q ≤ 105).

Each of the next q lines contains two integers ki and li  — the minimal and maximal number of coins that could be taken at one turn in the i-th round.

Output

Write q space-separated integers. The i-th number should be equal to the maximal possible length of the i-th round.

Examples
Input
10 2
1 1
5 6
Output
10 1