KTU Programming Camp (Day 5)
A. Queries
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Mathematicians are interesting (sometimes, I would say, even crazy) people. For example, my friend, a mathematician, thinks that it is very fun to play with a sequence of integer numbers. He writes the sequence in a row. If he wants he increases one number of the sequence, sometimes it is more interesting to decrease it (do you know why?..) And he likes to add the numbers in the interval [l;r]. But showing that he is really cool he adds only numbers which are equal some mod (modulo m).

Guess what he asked me, when he knew that I am a programmer? Yep, indeed, he asked me to write a program which could process these queries (n is the length of the sequence):

  • + p r It increases the number with index p by r. (, )

    You have to output the number after the increase.

  • - p r It decreases the number with index p by r. (, ) You must not decrease the number if it would become negative.

    You have to output the number after the decrease.

  • s l r mod You have to output the sum of numbers in the interval which are equal mod (modulo m). () ()
Input

The first line of each test case contains the number of elements of the sequence n and the number m. (1 ≤ n ≤ 10000) (1 ≤ m ≤ 10)

The second line contains n initial numbers of the sequence. (0 ≤ number ≤ 1000000000)

The third line of each test case contains the number of queries q (1 ≤ q ≤ 10000).

The following q lines contains the queries (one query per line).

Output

Output q lines - the answers to the queries.

Examples
Input
3 4
1 2 3
3
s 1 3 2
+ 2 1
- 1 2
Output
2
3
1
B. Personal programming language
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Everybody knows that you are not a real programmer until you create your own programming language. Informikas is aware of that too. Finally he is ready to become a real programmer.

Informikas doesn't want to create general purpose language (there are already so many of them!). He is creating a programming language to build text using functions.

The function in the programming language is declared and defined like this:

def f = word

Here "f" is a function name and "word" is the word returned by the function. For example, the following function would return "hello":

def h = hello

In addition, functions can be extended. To extend the function you add to function declaration with <function-name>. Only functions that are already declared can be used for extension. In the following example function f3 extends functions f1 and f2; function f5 extends f3 and f4; function f6 extends f3 and f2:

def f1 = world

def f2 = hello

def f3 with f2 with f1 = say

def f4 = please

def f5 with f3 with f4 = dont

def f6 with f3 with f2 = rather

Extending means that the function returns not a single word it defines, but also the words of extended functions. In the previous example calling the function "f3" would return the word defined in "f3", followed by the word defined in "f2" (the first function extended), following by the word defined in "f1" (the second function extended). The result of "f3" would be words "say hello world".

If the function extends other function which is also extending something, then the extensions gets propagated all the way down. In the previous example calling "f5" would result in string "dont say hello world please", because after flattening "f3" you would get:

f5 with f3 with f2 with f1 with f4

However, there is special case. If the same function gets extended multiple times, only the last occurrence would be left. For example, "f6" would be flattened to:

//flattened, but wrong – multiple occurence of "f2"

f6 with f3 with f2 with f1 with f2

//right, leaving only the last occurence of "f2"

f6 with f3 with f1 with f2

resulting in text "rather say world hello".

Knowing the syntax of the language, could you write a compiler which would compute the text returned?

Input

In the first line of input there is integer N (1 ≤ N ≤ 105) – the number of functions defined. In the following N lines there are N functions defined, in the format:

def Fi with Gi1 with Gi2 with ... with Gij = Wi

where Fi is the name of the function, Gi1, ... , Gij are the names of extended functions, Wi is the word returned by the function Fi. Each of Fi, Gij and Wi consists of [1;10] alphanumeric characters. In the last line there is a string H – the function being called, one of Fi.

It is guaranteed that function is used for extending (positions Gij) only if it was defined (position Fi) above. It is also guaranteed that the word "with" would be used no more than 105 times. In addition, words "def" and "with" are reserved and won't be used in place of neither Fi, Gij nor Wi (however, words "WITH", "wiTH", "Def", etc. are not reserved).

Output

Output the string which would be printed after calling function H.

Examples
Input
4
def a = one
def b with a = two
def c with a with b = three
def d with c = four
c
Output
three two one
Input
3
def a = sense
def b with a = make
def c with b with a with b = doesnt
c
Output
doesnt make sense
Note

This problem was inspired by how Scala programming language deals with multiple inheritance.

C. Reordering Ones
time limit per test
0.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Given a board of size N * M. The rows are numbered from 1 to N, and the columns are numbered from 1 to M. Each cell of the board contains either 0 or 1.

You can apply 2 types of operations:

  1. swapCol(i, j), meaning you can swap 2 different columns
  2. swapRow(i, j), meaning you can swap 2 different rows.

You have a function valid(x1, y1, x2, y2), which returns true if and only if every cell in the sub-board with 2 opposite corners (x1, y1), (x2, y2) contains all 1.

You need to find maximum value of (x0 + y0), such that it is possible to apply the operations, so that valid(1, 1, x0, y0) = true. However, everybody is only interested in solutions where x0 + y0 > max(m, n).

Input

On the first line of input there are two integers N and M (1 ≤ N, M ≤ 1000) – the size of the matrix. On the following N lines there are M integers each – the elements of the matrix, either 0 or 1.

Output

On the first line of output print the values x0 and y0 giving the maximal possible sum (x0 + y0).

On the next line of output print the number R – the number of operations.

On the following R lines output the operations itself in such format T i j, where T is the what is swapped ('C' for columns and 'R' for rows), i and j are the indexes of rows/columns being swapped.

If there are multiple solutions, output any of them.

If there is no solution such that x0 + y0 > max(m, n), print single line with "0 0".

Examples
Input
3 3
0 1 1
1 1 0
1 1 1
Output
1 3
1
R 1 3
Input
3 1
0
1
1
Output
0 0
D. Xor Sum
time limit per test
1 second
memory limit per test
4 megabytes
input
standard input
output
standard output

You're given an array a with n elements.

Compute the xor sum of the elements that appear an odd number of times in the array a.

Input

The first line contains number n (1 ≤ n ≤ 3000000). The second line of the input contains n numbers, representing the array a. All elements of a are between 0 and 109

Output

The only line of the output contains the answer of the problem.

Examples
Input
5
4 4 3 3 4
Output
4
E. Slicing cheese
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You have a polygon defined by N points (xi, yi) and a polyline defined by M points (aj, bj). Polyline cuts polygon into some number of smaller polygons. Find the total perimeter P of resulting polygons. Polyline is guaranteed to start and end outside of the polygon. Each segment of polyline has no more than 1 common point with any segment of polygon segments. All points in the input are distinct. (aj, bj) does not lie on any line segment of the polygon.

Input

First line contains integers N and M. (3 ≤ N ≤ 1000, 2 ≤ M ≤ 1000)

Next N lines contain integers xi and yi.

Next M lines contain integers aj and bj.

( - 105 ≤ xi, yi, aj, bj ≤ 105)

Output

Output a single number P.

The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples
Input
4 2
0 0
10 0
10 10
0 10
5 -1
5 11
Output
60.000000000000000
F. Matrix
time limit per test
0.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You're given a matrix with n rows and n columns. A basic property of a square matrix is the main diagonal: all cells that have the same row and column number.

We consider all diagonals that are parallel to the main one. We consider them from left-low corner to the right-upper one. So, the first cell of each diagonal will be, in order: (n, 1) (n - 1, 1) ... (1, 1) (1, 2) ... (1, n).

You need to choose one number from each diagonal. More, all 2*n-1 numbers must be pairwise distinct.

Input

The first line contains number n (1 ≤ n ≤ 300). Next n lines contain n numbers, representing the elements of the matrix. All elements of the matrix are between 1 and 109.

Output

If there is no solution, output "NO". Otherwise, output "YES". Next, on the same line, output 2n-1 numbers, separated by spaces. Each number represents the chosen value from a diagonal. Diagonals are considered in the order given by the problem.

Examples
Input
2
1 1
1 1
Output
NO
G. Yet Another Median Task
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You're given a matrix a with n lines and n columns. We define the median of an array the element from the middle position of sorted array. If there are two such positions (n is even), get the element whose position is minimal.

Answer q queries of form: what's the median element of a submatrix (x1, y1, x2, y2). Formally, we consider all elements a[i][j] such as x1 <= i <= x2 and y1 <= j <= y2 and add them into a temporary array. Then, get the median of the array.

Input

First line of the input contains numbers n (1 ≤ n ≤ 800) and q (1 ≤ q ≤ 1000). Next n lines contain n numbers, describing the 1-based matrix a. All elements from a can fit into an int type. Next q lines contain numbers x1, y1, x2, y2, describing a query (1 ≤ x1 ≤ x2 ≤ n , 1 ≤ y1 ≤ y2 ≤ n)

Output

Output q lines, each line to answer a query.

Examples
Input
2 4
1 2
2 2
1 1 2 1
1 1 1 2
1 1 2 2
2 2 2 2
Output
1
1
2
2
H. Packing circles
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You are given rectangle dimensions (W - width, H - height) and circle diameter D. How many circles can you fit inside that rectangle? Circles must be placed in rows parallel to the bottom. Each row must have the same amount of circles. Each pair of consecutive rows must have the same distance between them. A row is defined by a horizontal line. Circle belongs to a row if its center point lies on that line.

Input

A single line contains 3 integers W, H and D. (1 ≤ W, H, D ≤ 106)

Output

A single integer - the maximal amount of circles that can fit inside the rectangle with given restrictions.

Examples
Input
2 2 2
Output
1
Input
2 2 1
Output
4
I. Card Jousting
time limit per test
0.25 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

Iahub and Iahubina are playing a card game. Each of them has N cards on which are written numbers. Even if Iahub loves Iahubina very much, he wants to win this game. In order to do that he needs to win all the rounds. A round consists in the choice of the card by Iahubina which will be removed afterwords. Iahub also has to choose a card from his deck, which will be removed afterwords as well. Let B be the card chosen by Iahubina and A the card chosen by Iahub. Iahub can win only if A|B ≥ K. In addition, Iahub has the possibility to interchange the bits from any two cards, but with a cost. Iahub can interchange the bit i from any card from his deck with the bit j, the cost being cost[i][j]. Find the minimum cost which could lead Iahub to win.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 200). The second line contains a vector A[] with N elements, representing the numbers on Iahubina’s cards. The third line contains a vector B[] with N elements, representing the numbers on Iahub’s cards (1 ≤ A[i], B[i] ≤ 256) On the next line is the integer K (1 ≤ K ≤ 127), followed by 8 lines with 8 values per line, corresponding to the matrix cost[][] (1 ≤ cost[i][j] ≤ 1000, cost[i][j] = cost[j][i]).

Output

Output the minimum cost which would lead Iahub to win.

Examples
Input
5
127 115 18 81 12
9 73 60 70 19
127
9 7 10 7 5 1 6 1
7 1 9 1 10 2 10 7
10 9 10 9 10 5 10 9
7 1 9 1 5 10 6 7
5 10 10 5 2 3 4 10
1 2 5 10 3 8 5 5
6 10 10 6 4 5 7 1
1 7 9 7 10 5 1 10
Output
10
J. Empty Circle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set of n points S = {p1, p2, ..., pn} on the plane. A triple (pi, pj, pk) is called good if no point in S is strictly inside the circumference of these three points. If it is possible, find a good triple!

Input

The first line contains an integer n, the number of the points (3 ≤ n ≤ 106). The i-th of the next n lines contains two integer numbers xi and yi, the coordinates of pi ( - 104 ≤ xi, yi ≤ 104). No two given points will be equal.

Output

If a good triple exists, output "Yes" in the first line. In the next line output three space-separated integers, the numbers of the three points as they appeared in the input.

If no good triple exists, output "No" in a single line.

Examples
Input
4
0 1
0 0
-1 -1
1 -1
Output
Yes
3 1 2
Input
3
-1 -1
0 0
1 1
Output
No
Input
4
-2 -2
2 -2
-2 2
2 2
Output
Yes
1 3 2
n-Way Tie
time limit per test
0.3 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

In the country of Tieland, there is an annual tie tying tournament that hosts n participants numbered with integers from 1 to n. Each two participants meet exactly once and have a match in tie tying. There is a winner and a loser in each of the matches. A participant obtains a point for each match victory, and the loser gets zero points for that match. The score of the participant is the total number of points he earned.

However, the jury is worried of the scenario in which all participants have exactly the same score; in other words, there is an n-way tie. In that case any participant would be both the winner and the loser of the competition, which is absurd! Alas, the jury is tied up with the organisation of the tournament; help them and find out whether such a situation might occur!

Input

The single line of the input contains an integer n (1 ≤ n ≤ 1000), the number of participants.

Output

If such a scenario is possible, output "Yes" in the first line. Then output n - 1 lines, the i-th containing n - i space-separated integers. The j-th number of the i-th line aij should denote the outcome of the match between participants with numbers i and i + j:

  • aij = 1, if the i-th participant won the match;
  • aij = 0, if the (i + j)-th participant won the match.
If multiple solutions exists, output any of them.

If such a scenario is not possible, output "No" in a single line.

Examples
K. n-Way Tie
2
Output
No
Input
3
Output
Yes
1 0 
1
L. Basketball
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

The most important part of playing basketball in the yard is to choose two equally strong teams. Otherwise, the game could be ruined because the stronger team could win easily.

However, sometimes the number of players in the team is not so important. Especially, if tall guys are playing with small kids.

There are two teams: Reds and Blues. For each player in the teams we know his skills.

We are interested in how many ways we can choose some players from Reds and some players from Blues, so that the created teams are equally strong. The strength of the team is the sum of the skills of its individual players.

Input

The first line of each test case contains the number of players in Reds n and the number of players in Blues m (1 ≤ n, m) (n + m ≤ 17).

The second line of each test case contains the skills of players in Reds from 1 through n.

The third line of each test case contains the skills of players in Blues from 1 through m.

Skills are integers in the interval [1;100000000].

Output

Output the number of ways of choosing two equally strong teams.

Examples
Input
1 2
2
1 1
Output
1
Input
1 1
1
2
Output
0