Codeforces Round 194 (Div. 2)
A. Candy Bags
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

Gerald has n younger brothers and their number happens to be even. One day he bought n2 candy bags. One bag has one candy, one bag has two candies, one bag has three candies and so on. In fact, for each integer k from 1 to n2 he has exactly one bag with k candies.

Help him give n bags of candies to each brother so that all brothers got the same number of candies.

Input

The single line contains a single integer n (n is even, 2 ≤ n ≤ 100) — the number of Gerald's brothers.

Output

Let's assume that Gerald indexes his brothers with numbers from 1 to n. You need to print n lines, on the i-th line print n integers — the numbers of candies in the bags for the i-th brother. Naturally, all these numbers should be distinct and be within limits from 1 to n2. You can print the numbers in the lines in any order.

It is guaranteed that the solution exists at the given limits.

Examples
Input
2
Output
1 4
2 3
Note

The sample shows Gerald's actions if he has two brothers. In this case, his bags contain 1, 2, 3 and 4 candies. He can give the bags with 1 and 4 candies to one brother and the bags with 2 and 3 to the other brother.

B. Eight Point Sets
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

Gerald is very particular to eight point sets. He thinks that any decent eight point set must consist of all pairwise intersections of three distinct integer vertical straight lines and three distinct integer horizontal straight lines, except for the average of these nine points. In other words, there must be three integers x1, x2, x3 and three more integers y1, y2, y3, such that x1 < x2 < x3, y1 < y2 < y3 and the eight point set consists of all points (xi, yj) (1 ≤ i, j ≤ 3), except for point (x2, y2).

You have a set of eight points. Find out if Gerald can use this set?

Input

The input consists of eight lines, the i-th line contains two space-separated integers xi and yi (0 ≤ xi, yi ≤ 106). You do not have any other conditions for these points.

Output

In a single line print word "respectable", if the given set of points corresponds to Gerald's decency rules, and "ugly" otherwise.

Examples
Input
0 0
0 1
0 2
1 0
1 2
2 0
2 1
2 2
Output
respectable
Input
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
Output
ugly
Input
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
Output
ugly
C. Secrets
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

Gerald has been selling state secrets at leisure. All the secrets cost the same: n marks. The state which secrets Gerald is selling, has no paper money, only coins. But there are coins of all positive integer denominations that are powers of three: 1 mark, 3 marks, 9 marks, 27 marks and so on. There are no coins of other denominations. Of course, Gerald likes it when he gets money without the change. And all buyers respect him and try to give the desired sum without change, if possible. But this does not always happen.

One day an unlucky buyer came. He did not have the desired sum without change. Then he took out all his coins and tried to give Gerald a larger than necessary sum with as few coins as possible. What is the maximum number of coins he could get?

The formal explanation of the previous paragraph: we consider all the possible combinations of coins for which the buyer can not give Gerald the sum of n marks without change. For each such combination calculate the minimum number of coins that can bring the buyer at least n marks. Among all combinations choose the maximum of the minimum number of coins. This is the number we want.

Input

The single line contains a single integer n (1 ≤ n ≤ 1017).

Please, do not use the %lld specifier to read or write 64 bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

In a single line print an integer: the maximum number of coins the unlucky buyer could have paid with.

Examples
Input
1
Output
1
Input
4
Output
2
Note

In the first test case, if a buyer has exactly one coin of at least 3 marks, then, to give Gerald one mark, he will have to give this coin. In this sample, the customer can not have a coin of one mark, as in this case, he will be able to give the money to Gerald without any change.

In the second test case, if the buyer had exactly three coins of 3 marks, then, to give Gerald 4 marks, he will have to give two of these coins. The buyer cannot give three coins as he wants to minimize the number of coins that he gives.

D. Chips
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

Gerald plays the following game. He has a checkered field of size n × n cells, where m various cells are banned. Before the game, he has to put a few chips on some border (but not corner) board cells. Then for n - 1 minutes, Gerald every minute moves each chip into an adjacent cell. He moves each chip from its original edge to the opposite edge. Gerald loses in this game in each of the three cases:

  • At least one of the chips at least once fell to the banned cell.
  • At least once two chips were on the same cell.
  • At least once two chips swapped in a minute (for example, if you stand two chips on two opposite border cells of a row with even length, this situation happens in the middle of the row).

In that case he loses and earns 0 points. When nothing like that happened, he wins and earns the number of points equal to the number of chips he managed to put on the board. Help Gerald earn the most points.

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 105) — the size of the field and the number of banned cells. Next m lines each contain two space-separated integers. Specifically, the i-th of these lines contains numbers xi and yi (1 ≤ xi, yi ≤ n) — the coordinates of the i-th banned cell. All given cells are distinct.

Consider the field rows numbered from top to bottom from 1 to n, and the columns — from left to right from 1 to n.

Output

Print a single integer — the maximum points Gerald can earn in this game.

Examples
Input
3 1
2 2
Output
0
Input
3 0
Output
1
Input
4 3
3 1
3 2
3 3
Output
1
Note

In the first test the answer equals zero as we can't put chips into the corner cells.

In the second sample we can place one chip into either cell (1, 2), or cell (3, 2), or cell (2, 1), or cell (2, 3). We cannot place two chips.

In the third sample we can only place one chip into either cell (2, 1), or cell (2, 4).

E. Lucky Tickets
time limit per test
6 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Gerald has a friend, Pollard. Pollard is interested in lucky tickets (ticket is a sequence of digits). At first he thought that a ticket is lucky if between some its digits we can add arithmetic signs and brackets so that the result obtained by the arithmetic expression was number 100. But he quickly analyzed all such tickets and moved on to a more general question. Now he explores k-lucky tickets.

Pollard sais that a ticket is k-lucky if we can add arithmetic operation signs between its digits to the left or right of them (i.e., "+", "-", " × ") and brackets so as to obtain the correct arithmetic expression whose value would equal k. For example, ticket "224201016" is 1000-lucky as ( - 2 - (2 + 4)) × (2 + 0) + 1016 = 1000.

Pollard was so carried away by the lucky tickets that he signed up for a seminar on lucky tickets and, as far as Gerald knows, Pollard will attend it daily at 7 pm in some famous institute and will commute to it in the same tram for m days. In this tram tickets have eight digits. And Gerald wants to make a surprise for Pollard: each day Pollard will receive a tram k-lucky ticket. The conductor has already agreed to give Pollard certain tickets during all these m days and he only wants Gerald to tell him what kind of tickets to give out. In this regard, help Gerald pick exactly m distinct k-lucky tickets.

Input

The single line contains two integers k and m (0 ≤ k ≤ 104, 1 ≤ m ≤ 3·105).

Output

Print m lines. Each line must contain exactly 8 digits — the k-winning ticket. The tickets may begin with 0, all tickets must be distinct. If there are more than m distinct k-lucky tickets, print any m of them. It is guaranteed that at least m distinct k-lucky tickets exist. The tickets can be printed in any order.

Examples
Input
0 3
Output
00000000
00000001
00000002
Input
7 4
Output
00000007
00000016
00000017
00000018