vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given 'k' eggs and a 'n' storey building. The eggs MIGHT break if thrown down from a specific height (Note: It is NOT necessary that the eggs have to break; they might not even break from the topmost floor). What is the minimum number of steps in which you can find (using 'k' eggs) the minimum height of the floor in the building from which the eggs will start breaking ? 

Note: 

You have to output the minimum number of steps required; NOT the floor of the building from which eggs will break;

Input Format: 

First line of the input is an integer 'q':
1 ≤ q ≤ 1,000, which is the number of queries. 

Second line of the input has two space separated integers: the height of the building 'n' and the number of eggs which you can use 'k':
1 ≤ n ≤ 1,000
1 ≤ k ≤ 10

Output Format:

For each q output a single line denoting the minimum number of trials required to find the height from which the eggs will start breaking. 

Example:

For n = 151 and k = 1 the minimum number of steps in which we can find the height from which eggs can break(considering the worst case) is 151. This is because since we have only 1 egg we have no choice but to start from the first floor and throw the egg from each floor and check whether it breaks or not. In worst case this might require 151 steps. 

For n = 100 and k = 2 the minimum number of steps in which we can find the height from which eggs can break(considering again the worst case) is 14. This is because suppose we throw the FIRST egg from 14th floor and it breaks then we will have to try each of the remaining 13 floors using the remaining egg. So in this case number of trials required is 14. Suppose the first egg doesn't break then we can drop it from 27th floor (13 + 14). We have chosen 27th floor because suppose if the first egg breaks from 27th floor then we will have to test floors from 15-26 (=12). So, the total number of trials required in this case is: 12 + 1(from 14th floor) + 1(from 27th floor) = 14 trials. Suppose the first egg doesn't break even now, drop it from 39(12 + 13 + 14) floor for same reason. 

SAMPLE INPUT
4
10 1
10 2
100 2
104 3

SAMPLE OUTPUT
10
4
14
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Antimatter

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub accidentally discovered a secret lab. He found there *n* devices ordered in a line, numbered from 1 to *n* from left to right. Each device *i* (1<=≤<=*i*<=≤<=*n*) can create either *a**i* units of matter or *a**i* units of antimatter. 

Iahub wants to choose some contiguous subarray of devices in the lab, specify the production mode for each of them (produce matter or antimatter) and finally take a photo of it. However he will be successful only if the amounts of matter and antimatter produced in the selected subarray will be the same (otherwise there would be overflowing matter or antimatter in the photo). 

You are requested to compute the number of different ways Iahub can successful take a photo. A photo is different than another if it represents another subarray, or if at least one device of the subarray is set to produce matter in one of the photos and antimatter in the other one.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=1000). The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=1000).

The sum *a*1<=+<=*a*2<=+<=...<=+<=*a**n* will be less than or equal to 10000.

Output Specification:
Output a single integer, the number of ways Iahub can take a photo, modulo 1000000007 (109<=+<=7).

Demo Input:
['4\n1 1 1 1\n']

Demo Output:
['12\n']

Note:
The possible photos are [1+, 2-], [1-, 2+], [2+, 3-], [2-, 3+], [3+, 4-], [3-, 4+], [1+, 2+, 3-, 4-], [1+, 2-, 3+, 4-], [1+, 2-, 3-, 4+], [1-, 2+, 3+, 4-], [1-, 2+, 3-, 4+] and [1-, 2-, 3+, 4+], where "*i*+" means that the *i*-th element produces matter, and "*i*-" means that the *i*-th element produces antimatter.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bwahahahahaha!!! Your nemesis, the dashingly handsome spy Waco Powers, has at last fallen to your secret volcano base’s deathtraps (or so you assume, being a little too busy to witness it firsthand). At long last, you are all set to Conquer The World!

Nothing will stand in your way! Well, nothing except a minor problem of logistics. Your evil armies have announced that they will not continue carving their relentless path of destruction across the puny nations of the world without being paid. And unfortunately you are running low on cash – a volcano lair has many wonderful qualities, but “reasonably affordable” is not one of them. You have had to pull funds from the travel budget to pay your ungrateful underlings. Now you are not sure how you will actually get your armies into position to Conquer The World.

You have a map of the nations of the world and all your available transport routes between them. Each route connects two nations and has a fixed cost per army that uses it. The routes are laid out such that there is exactly one way to travel between any two nations. You know the current position of each of your armies and how many you will need to place permanently in each nation in order to subjugate it. How can you move the armies into place as cheaply as possible so you can Conquer The World?

-----Input-----
The first line of input contains an integer $n$ ($1 \le n \le 250000$), the number of nations. This is followed by $n-1$ lines, each containing three integers $u$, $v$, and $c$ ($1 \le u, v \le n$, $1 \le c \le 10^6$), indicating that there is a bidirectional route connecting nations $u$ and $v$, which costs $c$ per army to use.

Finally, another $n$ lines follow, the $i^{\text {th}}$ of which contains two non-negative integers $x_ i$ and $y_ i$, indicating that there are currently $x_ i$ armies in nation $i$, and you need at least $y_ i$ armies to end up in that nation in the final configuration. The total number of armies (the sum of the $x_ i$ values) is at least the sum of the $y_ i$ values, and no more than $10^6$.

-----Output-----
Display the minimum cost to move your armies such that there are at least $y_ i$ armies in nation $i$ for all $i$.

-----Examples-----
Sample Input:
3
1 2 5
3 1 5
2 1
5 0
1 3
Sample Output:
15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given integers c_{0}, c_{1}, …, c_{k-1} we can define the cost of a number 0 ≤ x < 2^{k} as p(x) = ∑_{i=0}^{k-1} \left( \left⌊ \frac{x}{2^{i}} \right⌋ mod 2 \right) ⋅ c_{i}. In other words, the cost of number x is the sum of c_{i} over the bits of x which are equal to one.

Let's define the cost of array a of length n ≥ 2 with elements from [0, 2^{k}) as follows: cost(a) = ∑_{i=1}^{n - 1} p(a_{i} ⊕ a_{i+1}), where ⊕ denotes [bitwise exclusive OR](https://en.wikipedia.org/wiki/Exclusive_or) operation.

You have to construct an array of length n with minimal cost, given that each element should belong to the given segment: l_{i} ≤ a_{i} ≤ r_{i}.

Input

The first line contains two integers n and k (2 ≤ n ≤ 50, 1 ≤ k ≤ 50) — the size of an array and bit length of the numbers in question.

Next n lines contain the restrictions for elements of the array: the i-th line contains two integers l_{i} and r_{i} (0 ≤ l_{i} ≤ r_{i} < 2^{k}).

The last line contains integers c_{0}, c_{1}, …, c_{k-1} (0 ≤ c_{i} ≤ 10^{12}).

Output

Output one integer — the minimal cost of an array satisfying all the restrictions.

Examples

Input


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


Output


30


Input


3 3
2 2
3 4
4 6
1 10 100


Output


102

Note

In the first example there is only one array satisfying all the restrictions — [3, 5, 6, 1] — and its cost is equal to cost([3, 5, 6, 1]) = p(3 ⊕ 5) + p(5 ⊕ 6) + p(6 ⊕ 1) = p(6) + p(3) + p(7) = (c_{1} + c_{2}) + (c_{0} + c_{1}) + (c_{0} + c_{1} + c_{2}) = (2 + 7) + (5 + 2) + (5 + 2 + 7) = 30.

In the second example the only optimal array is [2, 3, 6].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Greenhouse Effect

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Emuskald is an avid horticulturist and owns the world's longest greenhouse — it is effectively infinite in length.

Over the years Emuskald has cultivated *n* plants in his greenhouse, of *m* different plant species numbered from 1 to *m*. His greenhouse is very narrow and can be viewed as an infinite line, with each plant occupying a single point on that line.

Emuskald has discovered that each species thrives at a different temperature, so he wants to arrange *m*<=-<=1 borders that would divide the greenhouse into *m* sections numbered from 1 to *m* from left to right with each section housing a single species. He is free to place the borders, but in the end all of the *i*-th species plants must reside in *i*-th section from the left.

Of course, it is not always possible to place the borders in such way, so Emuskald needs to replant some of his plants. He can remove each plant from its position and place it anywhere in the greenhouse (at any real coordinate) with no plant already in it. Since replanting is a lot of stress for the plants, help Emuskald find the minimum number of plants he has to replant to be able to place the borders.

Input Specification:
The first line of input contains two space-separated integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=5000, *n*<=≥<=*m*), the number of plants and the number of different species. Each of the following *n* lines contain two space-separated numbers: one integer number *s**i* (1<=≤<=*s**i*<=≤<=*m*), and one real number *x**i* (0<=≤<=*x**i*<=≤<=109), the species and position of the *i*-th plant. Each *x**i* will contain no more than 6 digits after the decimal point.

It is guaranteed that all *x**i* are different; there is at least one plant of each species; the plants are given in order "from left to the right", that is in the ascending order of their *x**i* coordinates (*x**i*<=&lt;<=*x**i*<=+<=1,<=1<=≤<=*i*<=&lt;<=*n*).

Output Specification:
Output a single integer — the minimum number of plants to be replanted.

Demo Input:
['3 2\n2 1\n1 2.0\n1 3.100\n', '3 3\n1 5.0\n2 5.5\n3 6.0\n', '6 3\n1 14.284235\n2 17.921382\n1 20.328172\n3 20.842331\n1 25.790145\n1 27.204125\n']

Demo Output:
['1\n', '0\n', '2\n']

Note:
In the first test case, Emuskald can replant the first plant to the right of the last plant, so the answer is 1.

In the second test case, the species are already in the correct order, so no replanting is needed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are a number of people who will be attending ACM-ICPC World Finals. Each of them may be well versed in a number of topics. Given a list of topics known by each attendee, presented as binary strings, determine the maximum number of topics a 2-person team can know. Each subject has a column in the binary string, and a '1' means the subject is known while '0' means it is not.  Also determine the number of teams that know the maximum number of topics.  Return an integer array with two elements.  The first is the maximum number of topics known, and the second is the number of teams that know that number of topics.  

Example  

$n=3$ 

$to pics=[\text{'}10101\text{'},\text{'}11110\text{'},\text{'}00010\text{'}]$  

The attendee data is aligned for clarity below:

10101
11110
00010

These are all possible teams that can be formed:

Members Subjects
(1,2)   [1,2,3,4,5]
(1,3)   [1,3,4,5]
(2,3)   [1,2,3,4]

In this case, the first team will know all 5 subjects.  They are the only team that can be created that knows that many subjects, so $[5,1]$ is returned.

Function Description  

Complete the acmTeam function in the editor below. 

acmTeam has the following parameter(s):  

string topic: a string of binary digits  

Returns  

int[2]:  the maximum topics and the number of teams that know that many topics   

Input Format

The first line contains two space-separated integers $n$ and $m$, where $n$ is the number of attendees and $m$ is the number of topics.  

Each of the next $n$ lines contains a binary string of length $m$.  

Constraints

$2\leq n\leq500$ 

$1\leq m\leq500$ 

Sample Input
4 5
10101
11100
11010
00101

Sample Output
5
2

Explanation

Calculating topics known for all permutations of 2 attendees we get:  

$(1,2)\rightarrow4$ 

$(1,3)\rightarrow5$ 

$(1,4)\rightarrow3$ 

$(2,3)\rightarrow4$ 

$(2,4)\rightarrow4$ 

$(3,4)\rightarrow5$  

The 2 teams (1, 3) and (3, 4) know all 5 topics which is maximal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Egor wants to achieve a rating of 1600 points on the well-known chess portal ChessForces and he needs your help!

Before you start solving the problem, Egor wants to remind you how the chess pieces move. Chess rook moves along straight lines up and down, left and right, as many squares as it wants. And when it wants, it can stop. The queen walks in all directions vertically and diagonally at any distance. You can see the examples below.

<image>

To reach the goal, Egor should research the next topic:

There is an N × N board. Each cell of the board has a number from 1 to N ^ 2 in it and numbers in all cells are distinct.

In the beginning, some chess figure stands in the cell with the number 1. Note that this cell is already considered as visited. After that every move is determined by the following rules: 

  1. Among all not visited yet cells to which the figure can get in one move, it goes to the cell that has minimal number.
  2. If all accessible cells were already visited and some cells are not yet visited, then the figure is teleported to the not visited cell that has minimal number. If this step happens, the piece pays a fee of 1 vun.
  3. If all cells are already visited, the process is stopped. 



Egor should find an N × N board on which the rook pays strictly less vuns than the queen during the round with this numbering. Help him to find such N × N numbered board, or tell that it doesn't exist.

Input

The only line contains one integer N — the size of the board, 1≤ N ≤ 500.

Output

The output should contain N lines.

In i-th line output N numbers — numbers on the i-th row of the board. All numbers from 1 to N × N must be used exactly once.

On your board rook must pay strictly less vuns than the queen.

If there are no solutions, print -1.

If there are several solutions, you can output any of them. 

Examples

Input


1


Output


-1

Input


4


Output


4 3 6 12 
7 5 9 15 
14 1 11 10 
13 8 16 2 

Note

In case we have 1 × 1 board, both rook and queen do not have a chance to pay fees.

In second sample rook goes through cells 1 → 3 → 4 → 6 → 9 → 5 → 7 → 13 → 2 → 8 → 16 → 11 → 10 → 12 → 15 → (1 vun) → 14. 

Queen goes through 1 → 3 → 4 → 2 → 5 → 6 → 9 → 7 → 13 → 8 → 11 → 10 → 12 → 15 → (1 vun) → 14 → (1 vun) → 16.

As a result rook pays 1 vun and queen pays 2 vuns.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer S. Find the largest even number that can be formed by rearranging the digits of S.
Note: In case the number does not contain any even digit then output the largest odd number possible.
Example 1:
Input:
S = "1324"
Output: "4312"
Explanation: Largest even number: 4312
Example 2:
Input:
S = "3555"
Output: "5553"
Explanation: No even number possible,
So we'll find largest odd number.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function LargestEven() which takes the string S as inputs representing the integer and returns the answer.
Expected Time Complexity: O(|S| * log |S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}
S contains only digits from '0' to '9'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Facetook is a well known social network website, and it will launch a new feature called Facetook Priority Wall. This feature will sort all posts from your friends according to the priority factor (it will be described).

This priority factor will be affected by three types of actions: 

  * 1. "X posted on Y's wall" (15 points), 
  * 2. "X commented on Y's post" (10 points), 
  * 3. "X likes Y's post" (5 points). 



X and Y will be two distinct names. And each action will increase the priority factor between X and Y (and vice versa) by the above value of points (the priority factor between X and Y is the same as the priority factor between Y and X).

You will be given n actions with the above format (without the action number and the number of points), and you have to print all the distinct names in these actions sorted according to the priority factor with you.

Input

The first line contains your name. The second line contains an integer n, which is the number of actions (1 ≤ n ≤ 100). Then n lines follow, it is guaranteed that each one contains exactly 1 action in the format given above. There is exactly one space between each two words in a line, and there are no extra spaces. All the letters are lowercase. All names in the input will consist of at least 1 letter and at most 10 small Latin letters.

Output

Print m lines, where m is the number of distinct names in the input (excluding yourself). Each line should contain just 1 name. The names should be sorted according to the priority factor with you in the descending order (the highest priority factor should come first). If two or more names have the same priority factor, print them in the alphabetical (lexicographical) order.

Note, that you should output all the names that are present in the input data (excluding yourself), even if that person has a zero priority factor.

The lexicographical comparison is performed by the standard "<" operator in modern programming languages. The line a is lexicographically smaller than the line b, if either a is the prefix of b, or if exists such an i (1 ≤ i ≤ min(|a|, |b|)), that ai < bi, and for any j (1 ≤ j < i) aj = bj, where |a| and |b| stand for the lengths of strings a and b correspondently.

Examples

Input

ahmed
3
ahmed posted on fatma's wall
fatma commented on ahmed's post
mona likes ahmed's post


Output

fatma
mona


Input

aba
1
likes likes posted's post


Output

likes
posted

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
__Definition:__ According to Wikipedia, a [complete binary tree](https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees) is a binary tree _"where every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible."_

The Wikipedia page referenced above also mentions that _"Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space."_

Your task is to write a method (or function) that takes an array (or list, depending on language) of integers and, assuming that the array is ordered according to an _in-order_ traversal of a complete binary tree, returns an array that contains the values of the tree in breadth-first order.

__Example 1:__
Let the input array be `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`. This array contains the values of the following complete binary tree. 


```
          _ 7_
        /      \
       4        9
     /   \     / \
   2      6   8   10
  / \     /
 1   3   5
```
In this example, the input array happens to be sorted, but that is _not_ a requirement.

__Output 1:__ The output of the function shall be an array containing the values of the nodes of the binary tree read top-to-bottom, left-to-right. In this example, the returned array should be:

```[7, 4, 9, 2, 6, 8, 10, 1, 3, 5]```


__Example 2:__
Let the input array be `[1, 2, 2, 6, 7, 5]`. This array contains the values of the following complete binary tree. 


```
        6
      /   \
    2       5
   / \     /
  1   2   7
 
```
Note that an in-order traversal of this tree produces the input array.

__Output 2:__ The output of the function shall be an array containing the values of the nodes of the binary tree read top-to-bottom, left-to-right. In this example, the returned array should be:

```[6, 2, 5, 1, 2, 7]```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a permutation P[1... N] of integers from 1 to N, function f is defined as follows:

 $f(i, j) = \left\{\begin{array}{ll}{P [ i ]} & {\text{if} j = 1} \\{f(P [ i ], j - 1)} & {\text{otherwise}} \end{array} \right.$ 

Let g(i) be the minimum positive integer j such that f(i, j) = i. We can show such j always exists.

For given N, A, B, find a permutation P of integers from 1 to N such that for 1 ≤ i ≤ N, g(i) equals either A or B.


-----Input-----

The only line contains three integers N, A, B (1 ≤ N ≤ 10^6, 1 ≤ A, B ≤ N).


-----Output-----

If no such permutation exists, output -1. Otherwise, output a permutation of integers from 1 to N.


-----Examples-----
Input
9 2 5

Output
6 5 8 3 4 1 9 2 7
Input
3 2 1

Output
1 2 3 


-----Note-----

In the first example, g(1) = g(6) = g(7) = g(9) = 2 and g(2) = g(3) = g(4) = g(5) = g(8) = 5 

In the second example, g(1) = g(2) = g(3) = 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $b_1, b_2, \ldots, b_n$. Find the lexicographically minimal permutation $a_1, a_2, \ldots, a_{2n}$ such that $b_i = \min(a_{2i-1}, a_{2i})$, or determine that it is impossible.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$).

The first line of each test case consists of one integer $n$ — the number of elements in the sequence $b$ ($1 \le n \le 100$).

The second line of each test case consists of $n$ different integers $b_1, \ldots, b_n$ — elements of the sequence $b$ ($1 \le b_i \le 2n$).

It is guaranteed that the sum of $n$ by all test cases doesn't exceed $100$.


-----Output-----

For each test case, if there is no appropriate permutation, print one number $-1$.

Otherwise, print $2n$ integers $a_1, \ldots, a_{2n}$ — required lexicographically minimal permutation of numbers from $1$ to $2n$.


-----Example-----
Input
5
1
1
2
4 1
3
4 1 3
4
2 3 4 5
5
1 5 7 2 8

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Robot Vacuum Cleaner

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pushok the dog has been chasing Imp for a few hours already.

Fortunately, Imp knows that Pushok is afraid of a robot vacuum cleaner. 

While moving, the robot generates a string *t* consisting of letters 's' and 'h', that produces a lot of noise. We define noise of string *t* as the number of occurrences of string "sh" as a subsequence in it, in other words, the number of such pairs (*i*,<=*j*), that *i*<=&lt;<=*j* and  and . 

The robot is off at the moment. Imp knows that it has a sequence of strings *t**i* in its memory, and he can arbitrary change their order. When the robot is started, it generates the string *t* as a concatenation of these strings in the given order. The noise of the resulting string equals the noise of this concatenation.

Help Imp to find the maximum noise he can achieve by changing the order of the strings.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=105) — the number of strings in robot's memory.

Next *n* lines contain the strings *t*1,<=*t*2,<=...,<=*t**n*, one per line. It is guaranteed that the strings are non-empty, contain only English letters 's' and 'h' and their total length does not exceed 105.

Output Specification:
Print a single integer — the maxumum possible noise Imp can achieve by changing the order of the strings.

Demo Input:
['4\nssh\nhs\ns\nhhhs\n', '2\nh\ns\n']

Demo Output:
['18\n', '1\n']

Note:
The optimal concatenation in the first sample is *ssshhshhhs*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.