vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
One fine day, when everything was going good, Mehta was fired from his job and had to leave all the work.
So, he decided to become a member of gangster squad and start his new career of robbing.
Being a novice, mehta was asked to perform a robbery task in which he was given a bag having a capacity W units.
So, when he reached the house to be robbed, there lay N items each having particular weight and particular profit associated with it.
But, theres a twist associated, He has first 10 primes with him, which he can use atmost once, if he picks any item x, then he can multiply his profit[x] with any of the first 10 primes and then put that item into his bag. Each prime can only be used with one particular item and one item can only have atmost one prime multiplied with its profit. Its not necessary to pick all the items. If he doesnt want to use a prime with any particular item, he can simply add the profit as it is, more specifically, 1*profit[x] for xth item will get added to its total profit, and that he can do with as many items as he wants. He cannot fill his bag more than weight W units. Each item should be picked with its whole weight, i.e it cannot be broken into several other items of lesser weight. So, now to impress his squad, he wishes to maximize the total profit he can achieve by robbing this wealthy house.

Input:

First Line of input containts two integers N and W.
Next N lines contain information of ith item, describing profit and weight of the ith item, profit and weight are separated by single space.

Output:

In a single line, output the maximum profit obtainable.

Constraints:

1 ≤ N ≤ 2000, 1 ≤ W ≤ 2000

1 ≤ Profit[i] ≤ 10^9, 1 ≤ Weight[i] ≤ 2000

Explanation:

As all, the items can be picked, so maximum profit is equal to = 1 X 19 + 2 X 23 + 3 X 29 = 152

SAMPLE INPUT
3 4
1 1
2 1
3 1

SAMPLE OUTPUT
152

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a uniformly randomly generated string S, consisting of letters from the set {"A", "B"}. Your task is to find a string T that appears in S as a subsequence exactly twice.
In other words, you need to find such a string T, that there exist exactly two sets of indexes i1, i2, ..., i|T| and j1, j2, ..., j|T| such that there exists some k, where  ik ≠ jk and S{i1...i|T|} = S{j1...j|T|} = T.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a single string S.
The string S was generated randomly. For a generating string S, we first choose an integer N denoting a length of S. After that every symbol of the string S is chosen randomly from the set {"A", "B"} and the both symbols have equal probability to be chosen. Note that N is not choosen randomly.

Output
For each test case, output a string that occurs exactly twice as a subsequence in S, or output -1 if there is no such string. If there are more than one possible subsequences occurring exactly two times, you can print any one of them.

Constraints

1 ≤ T ≤ 10


Example
Input:
2
AAAA
BAB

Output:
-1
B

Explanation
Test case #1: 

The string "AAAA" appears once as a subsequence in itself.
The string "AAA" appears four times as a subsequence in "AAAA"; possible positions: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}.
The strings "AA" and "A" also appear in "AAAA" as a subsequence strictly more than twice.

So, there is no string of "AAAA", which appears exactly twice. Hence answer is -1.
Test case #2: Two occurrences of "B" in "BAB" are {1} and {3} (1-based indexing).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp loves not only to take pictures, but also to show his photos to friends. On his personal website he has recently installed a widget that can display n photos with the scroll option. At each moment of time the widget displays exactly one photograph with the option showing the previous/next one. From the first photo, you can switch to the second one or to the n-th one, from the second photo you can switch to the third one or to the first one, etc. Thus, navigation is performed in a cycle.

Polycarp's collection consists of m photo albums, the i-th album contains ai photos. Polycarp wants to choose n photos and put them on a new widget. To make watching the photos interesting to the visitors, he is going to post pictures so that no two photos from one album were neighboring (each photo will have exactly two neighbors, the first photo's neighbors are the second and the n-th one).

Help Polycarp compile a photo gallery. Select n photos from his collection and put them in such order that no two photos from one album went one after the other.

Input

The first line contains two integers n and m (3 ≤ n ≤ 1000, 1 ≤ m ≤ 40), where n is the number of photos on the widget, and m is the number of albums. The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 1000), where ai is the number of photos in the i-th album.

Output

Print the single number -1 if there is no solution. Otherwise, print n numbers t1, t2, ..., tn, where ti represents the number of the album of the i-th picture in the widget. The albums are numbered from 1 in the order of their appearance in the input. If there are several solutions, print any of them.

Examples

Input

4 3
1 3 5


Output

3 1 3 2


Input

10 2
5 5


Output

2 1 2 1 2 1 2 1 2 1


Input

10 3
1 10 3


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Singh is getting bored at work. He has a lot of ideas (N) to work on (as side projects) but is unable to choose one.

He chooses a random number (R) and lines up his ideas in a circle. He starts counting from first and removes the R^th idea in the circle until only one remains. Help him choose an idea to work on.

Input Format:

no_of_ideas random_number

Output Format:

idea_number

Constraints:

1 ≤ N ≤ 20

1 ≤ R ≤ 10000000

SAMPLE INPUT
5 3

SAMPLE OUTPUT
4

Explanation

List: {1,2,3,4,5}. Start counting from 1,

1 2 3 -> 3 removed

4 5 1 -> 1 removed

2 4 5 -> 5 removed

2 4 2 -> 2 removed

Remaining number: 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On an endless checkered sheet of paper, n cells are chosen and colored in three colors, where n is divisible by 3. It turns out that there are exactly n/3 marked cells of each of three colors! 

Find the largest such k that it's possible to choose k/3 cells of each color, remove all other marked cells, and then select three rectangles with sides parallel to the grid lines so that the following conditions hold:

  * No two rectangles can intersect (but they can share a part of the boundary). In other words, the area of intersection of any two of these rectangles must be 0.
  * The i-th rectangle contains all the chosen cells of the i-th color and no chosen cells of other colors, for i = 1, 2, 3. 

Input

The first line of the input contains a single integer n — the number of the marked cells (3 ≤ n ≤ 10^5, n is divisible by 3).

The i-th of the following n lines contains three integers x_i, y_i, c_i (|x_i|,|y_i| ≤ 10^9; 1 ≤ c_i ≤ 3), where (x_i, y_i) are the coordinates of the i-th marked cell and c_i is its color.

It's guaranteed that all cells (x_i, y_i) in the input are distinct, and that there are exactly n/3 cells of each color.

Output

Output a single integer k — the largest number of cells you can leave.

Examples

Input


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


Output


6


Input


3
1 1 1
2 2 2
3 3 3


Output


3

Note

In the first sample, it's possible to leave 6 cells with indexes 1, 5, 6, 7, 8, 9.

In the second sample, it's possible to leave 3 cells with indexes 1, 2, 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two positive integers n and k, the binary string  Sn is formed as follows:

S1 = "0"
Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).
For example, the first 4 strings in the above sequence are:

S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.
 
Example 1:
Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".

Example 2:
Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".

Example 3:
Input: n = 1, k = 1
Output: "0"

Example 4:
Input: n = 2, k = 3
Output: "1"

 
Constraints:

1 <= n <= 20
1 <= k <= 2n - 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You came to a brand-new aqua park. In this aqua park you are not sliding like in most of aqua parks, but falling.
There are N objects. Each object is non-horizontal and non-vertical segment. When you fall on the segment you start sliding on it and when you reach its lowest point you continue falling vertically. Then you can fall on another segment and so on until you reach the water.

You know your initial X coordinate and you are at very high altitude. Find your  final X coordinate.

Input 
The first line contains 2 space-separated integers - yout initial X coordinate and N - nunber of segment-objects.
The following N lines describe one object each by 4 space-separated integers x1, y1, x2, y2 - coordinates of the leftmost point of the object and the rightmost.
Objects doesn't intersect or touch each other.

Outout 
Output one integer - answer for the question.

Constraints
0 ≤ N ≤ 100
0 ≤ X ≤ 10^4
0 ≤x1, y1, x2, y2 ≤ 10^4
x1 < x2

SAMPLE INPUT
4 2
0 1 2 2
2 4 4 5


SAMPLE OUTPUT
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N pieces of source code. The characteristics of the i-th code is represented by M integers A_{i1}, A_{i2}, ..., A_{iM}.
Additionally, you are given integers B_1, B_2, ..., B_M and C.
The i-th code correctly solves this problem if and only if A_{i1} B_1 + A_{i2} B_2 + ... + A_{iM} B_M + C > 0.
Among the N codes, find the number of codes that correctly solve this problem.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, M \leq 20
 - -100 \leq A_{ij} \leq 100
 - -100 \leq B_i \leq 100
 - -100 \leq C \leq 100

-----Input-----
Input is given from Standard Input in the following format:
N M C
B_1 B_2 ... B_M
A_{11} A_{12} ... A_{1M}
A_{21} A_{22} ... A_{2M}
\vdots
A_{N1} A_{N2} ... A_{NM}

-----Output-----
Print the number of codes among the given N codes that correctly solve this problem.

-----Sample Input-----
2 3 -10
1 2 3
3 2 1
1 2 2

-----Sample Output-----
1

Only the second code correctly solves this problem, as follows:
 - Since 3 \times 1 + 2 \times 2 + 1 \times 3 + (-10) = 0 \leq 0, the first code does not solve this problem.
 - 1 \times 1 + 2 \times 2 + 2 \times 3 + (-10) = 1 > 0, the second code solves this problem.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# A History Lesson

The Pony Express was a mail service operating in the US in 1859-60.





It reduced the time for messages to travel between the Atlantic and Pacific coasts to about 10 days, before it was made obsolete by the transcontinental telegraph.

# How it worked

There were a number of *stations*, where:


* The rider switched to a fresh horse and carried on, or

* The mail bag was handed over to the next rider


# Kata Task


`stations` is a list/array of distances (miles) from one station to the next along the Pony Express route.

Implement the `riders` method/function, to return how many riders are necessary to get the mail from one end to the other.

##  Missing rider

In this version of the Kata a rider may go missing. In practice, this could be for a number of reasons - a lame horse, an accidental fall, foul play... 

After some time, the rider's absence would be noticed at the **next** station, so the next designated rider from there would have to back-track the mail route to look for his missing colleague. The missing rider is then safely escorted back to the station he last came from, and the mail bags are handed to his rescuer (or another substitute rider if necessary). 

`stationX` is the number (2..N) of the station where the rider's absence was noticed.

# Notes

* Each rider travels as far as he can, but never more than 100 miles.

# Example

GIven

* `stations = [43, 23, 40, 13]`

* `stationX = 4`

So

`S1` ...  ... 43 ...  ... `S2` ...  ... 23 ...  ... `S3` ...  ... 40 ...  ... `S4` ...  ... 13 ...  ... `S5`

* Rider 1 gets as far as Station S3
* Rider 2 (at station S3) takes mail bags from Rider 1
* Rider 2 never arrives at station S4
* Rider 3 goes back to find what happened to Rider 2
* Rider 2 and Rider 3 return together back to Station S3
* Rider 3 takes mail bags from Rider 2
* Rider 3 completes the journey to Station S5

**Answer:** 
3 riders




*Good Luck.
DM.*

---

See also
* The Pony Express
* The Pony Express (missing rider)

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

There are N sets of integers. Each of these sets is assigned a number from 1 to N. The number of elements in the i-th set is Ki, and the j-th smallest integer in the elements of the set is ai, j.

Taro decided to choose any number of sets from this. Taro, who thought it would be boring to just choose the right one, decided to choose at least three sets. In addition, we decided to select the product so that the product of "the number of elements in the union of the selected set" and "the number of elements in the intersection of the selected set" is as large as possible.

When Taro selects the optimal set, find the maximum value of the product of "the number of elements in the union of the selected set" and "the number of elements in the intersection of the selected set".

Constraints

The input satisfies the following conditions.

* All inputs are integers.
* 3 ≤ N ≤ 20,000
* 1 ≤ ai, j ≤ 22
* ai, j <ai, j + 1 (1 ≤ i ≤ N) (1 ≤ j <Ki)

Input

The input is given in the following format.


N
K1 a1,1 a1,2 ... a1, K1
K2 a2,1 a2,2 ... a2, K2
...
KN aN, 1 aN, 2 ... aN, KN


Output

Output the maximum value of the product of "the number of elements in the union of the selected set" and "the number of elements in the intersection of the selected set" when Taro chose optimally.

Examples

Input

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


Output

8


Input

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


Output

9


Input

3
2 3 4
2 2 5
2 1 6


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In some other world, today is Christmas Eve.
There are N trees planted in Mr. Takaha's garden. The height of the i-th tree (1 \leq i \leq N) is h_i meters.
He decides to choose K trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the decorated trees should be as close to each other as possible.
More specifically, let the height of the tallest decorated tree be h_{max} meters, and the height of the shortest decorated tree be h_{min} meters. The smaller the value h_{max} - h_{min} is, the better. What is the minimum possible value of h_{max} - h_{min}?

-----Constraints-----
 - 2 \leq K < N \leq 10^5
 - 1 \leq h_i \leq 10^9
 - h_i is an integer.

-----Input-----
Input is given from Standard Input in the following format:
N K
h_1
h_2
:
h_N

-----Output-----
Print the minimum possible value of h_{max} - h_{min}.

-----Sample Input-----
5 3
10
15
11
14
12

-----Sample Output-----
2

If we decorate the first, third and fifth trees, h_{max} = 12, h_{min} = 10 so h_{max} - h_{min} = 2. This is optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number as string(n) , find the remainder of the number when it is divided by 7
Example 1:
Input:
5
Output:
5
 
Example 2:
Input:
8
Output:
1
 
Your Task: 
You only need to complete the function remainderwith7() that takes string n as parameter and returns an integer which denotes the remainder of the number when its divided by 7
 
Constraints:
1<=length of n <=105

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
At the big break Nastya came to the school dining room. There are $n$ pupils in the school, numbered from $1$ to $n$. Unfortunately, Nastya came pretty late, so that all pupils had already stood in the queue, i.e. Nastya took the last place in the queue. Of course, it's a little bit sad for Nastya, but she is not going to despond because some pupils in the queue can agree to change places with some other pupils.

Formally, there are some pairs $u$, $v$ such that if the pupil with number $u$ stands directly in front of the pupil with number $v$, Nastya can ask them and they will change places. 

Nastya asks you to find the maximal number of places in queue she can move forward. 


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 3 \cdot 10^{5}$, $0 \leq m \leq 5 \cdot 10^{5}$) — the number of pupils in the queue and number of pairs of pupils such that the first one agrees to change places with the second one if the first is directly in front of the second.

The second line contains $n$ integers $p_1$, $p_2$, ..., $p_n$ — the initial arrangement of pupils in the queue, from the queue start to its end ($1 \leq p_i \leq n$, $p$ is a permutation of integers from $1$ to $n$). In other words, $p_i$ is the number of the pupil who stands on the $i$-th position in the queue.

The $i$-th of the following $m$ lines contains two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n, u_i \neq v_i$), denoting that the pupil with number $u_i$ agrees to change places with the pupil with number $v_i$ if $u_i$ is directly in front of $v_i$. It is guaranteed that if $i \neq j$, than $v_i \neq v_j$ or $u_i \neq u_j$. Note that it is possible that in some pairs both pupils agree to change places with each other.

Nastya is the last person in the queue, i.e. the pupil with number $p_n$.


-----Output-----

Print a single integer — the number of places in queue she can move forward.


-----Examples-----
Input
2 1
1 2
1 2

Output
1
Input
3 3
3 1 2
1 2
3 1
3 2

Output
2
Input
5 2
3 1 5 4 2
5 2
5 4

Output
1


-----Note-----

In the first example Nastya can just change places with the first pupil in the queue.

Optimal sequence of changes in the second example is   change places for pupils with numbers $1$ and $3$.  change places for pupils with numbers $3$ and $2$.  change places for pupils with numbers $1$ and $2$. 

The queue looks like $[3, 1, 2]$, then $[1, 3, 2]$, then $[1, 2, 3]$, and finally $[2, 1, 3]$ after these operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to construct a building which will be a pile of n cubes.
The cube at the bottom will have a volume of n^3, the cube above 
will have  volume of (n-1)^3 and so on until the top which will have a volume of 1^3.

You are given the total volume m of the building.
Being given m can you find the number n of cubes you will have to build?

The parameter of the function findNb `(find_nb, find-nb, findNb)` will be an integer m
and you have to return the integer n such as
n^3 + (n-1)^3 + ... + 1^3 = m
if such a n exists or -1 if there is no such n.

## Examples:
```
findNb(1071225) --> 45
findNb(91716553919377) --> -1
```

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Petya is the most responsible worker in the Research Institute. So he was asked to make a very important experiment: to melt the chocolate bar with a new laser device. The device consists of a rectangular field of *n*<=×<=*m* cells and a robotic arm. Each cell of the field is a 1<=×<=1 square. The robotic arm has two lasers pointed at the field perpendicularly to its surface. At any one time lasers are pointed at the centres of some two cells. Since the lasers are on the robotic hand, their movements are synchronized — if you move one of the lasers by a vector, another one moves by the same vector.

The following facts about the experiment are known: 
 -  initially the whole field is covered with a chocolate bar of the size *n*<=×<=*m*, both lasers are located above the field and are active; -  the chocolate melts within one cell of the field at which the laser is pointed; -  all moves of the robotic arm should be parallel to the sides of the field, after each move the lasers should be pointed at the centres of some two cells; -  at any one time both lasers should be pointed at the field. Petya doesn't want to become a second Gordon Freeman. 
You are given *n*, *m* and the cells (*x*1,<=*y*1) and (*x*2,<=*y*2), where the lasers are initially pointed at (*x**i* is a column number, *y**i* is a row number). Rows are numbered from 1 to *m* from top to bottom and columns are numbered from 1 to *n* from left to right. You are to find the amount of cells of the field on which the chocolate can't be melted in the given conditions.

Input Specification:
The first line contains one integer number *t* (1<=≤<=*t*<=≤<=10000) — the number of test sets. Each of the following *t* lines describes one test set. Each line contains integer numbers *n*, *m*, *x*1, *y*1, *x*2, *y*2, separated by a space (2<=≤<=*n*,<=*m*<=≤<=109, 1<=≤<=*x*1,<=*x*2<=≤<=*n*, 1<=≤<=*y*1,<=*y*2<=≤<=*m*). Cells (*x*1,<=*y*1) and (*x*2,<=*y*2) are distinct.

Output Specification:
Each of the *t* lines of the output should contain the answer to the corresponding input test set.

Demo Input:
['2\n4 4 1 1 3 3\n4 3 1 1 2 2\n']

Demo Output:
['8\n2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program to take two numbers as input and print their difference if the first number is greater than the second number otherwise$otherwise$ print their sum.

-----Input:-----
- First line will contain the first number (N1$N1$)
- Second line will contain the second number (N2$N2$)

-----Output:-----
Output a single line containing the difference of 2 numbers (N1−N2)$(N1 - N2)$ if the first number is greater than the second number otherwise output their sum (N1+N2)$(N1 + N2)$.

-----Constraints-----
- −1000≤N1≤1000$-1000 \leq N1 \leq 1000$
- −1000≤N2≤1000$-1000 \leq N2 \leq 1000$

-----Sample Input:-----
82
28

-----Sample Output:-----
54

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