vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As you know, lemmings like jumping. For the next spectacular group jump n lemmings gathered near a high rock with k comfortable ledges on it. The first ledge is situated at the height of h meters, the second one is at the height of 2h meters, and so on (the i-th ledge is at the height of i·h meters). The lemmings are going to jump at sunset, and there's not much time left.

Each lemming is characterized by its climbing speed of vi meters per minute and its weight mi. This means that the i-th lemming can climb to the j-th ledge in <image> minutes.

To make the jump beautiful, heavier lemmings should jump from higher ledges: if a lemming of weight mi jumps from ledge i, and a lemming of weight mj jumps from ledge j (for i < j), then the inequation mi ≤ mj should be fulfilled.

Since there are n lemmings and only k ledges (k ≤ n), the k lemmings that will take part in the jump need to be chosen. The chosen lemmings should be distributed on the ledges from 1 to k, one lemming per ledge. The lemmings are to be arranged in the order of non-decreasing weight with the increasing height of the ledge. In addition, each lemming should have enough time to get to his ledge, that is, the time of his climb should not exceed t minutes. The lemmings climb to their ledges all at the same time and they do not interfere with each other.

Find the way to arrange the lemmings' jump so that time t is minimized.

Input

The first line contains space-separated integers n, k and h (1 ≤ k ≤ n ≤ 105, 1 ≤ h ≤ 104) — the total number of lemmings, the number of ledges and the distance between adjacent ledges.

The second line contains n space-separated integers m1, m2, ..., mn (1 ≤ mi ≤ 109), where mi is the weight of i-th lemming.

The third line contains n space-separated integers v1, v2, ..., vn (1 ≤ vi ≤ 109), where vi is the speed of i-th lemming.

Output

Print k different numbers from 1 to n — the numbers of the lemmings who go to ledges at heights h, 2h, ..., kh, correspondingly, if the jump is organized in an optimal way. If there are multiple ways to select the lemmings, pick any of them.

Examples

Input

5 3 2
1 2 3 2 1
1 2 1 2 10


Output

5 2 4


Input

5 3 10
3 4 3 2 1
5 4 3 2 1


Output

4 3 1

Note

Let's consider the first sample case. The fifth lemming (speed 10) gets to the ledge at height 2 in <image> minutes; the second lemming (speed 2) gets to the ledge at height 4 in 2 minutes; the fourth lemming (speed 2) gets to the ledge at height 6 in 3 minutes. All lemmings manage to occupy their positions in 3 minutes. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently Vasya found a golden ticket — a sequence which consists of $n$ digits $a_1a_2\dots a_n$. Vasya considers a ticket to be lucky if it can be divided into two or more non-intersecting segments with equal sums. For example, ticket $350178$ is lucky since it can be divided into three segments $350$, $17$ and $8$: $3+5+0=1+7=8$. Note that each digit of sequence should belong to exactly one segment.

Help Vasya! Tell him if the golden ticket he found is lucky or not.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 100$) — the number of digits in the ticket.

The second line contains $n$ digits $a_1 a_2 \dots a_n$ ($0 \le a_i \le 9$) — the golden ticket. Digits are printed without spaces.


-----Output-----

If the golden ticket is lucky then print "YES", otherwise print "NO" (both case insensitive).


-----Examples-----
Input
5
73452

Output
YES

Input
4
1248

Output
NO



-----Note-----

In the first example the ticket can be divided into $7$, $34$ and $52$: $7=3+4=5+2$.

In the second example it is impossible to divide ticket into segments with equal sum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)
Given an array A of integers, return the length of the longest mountain. 
Return 0 if there is no mountain.
Example 1:
Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:
Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Follow up:

Can you solve it using only one pass?
Can you solve it in O(1) space?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix has decided to become a scientist! He is currently investigating the growth of bacteria.

Initially, on day 1, there is one bacterium with mass 1.

Every day, some number of bacteria will split (possibly zero or all). When a bacterium of mass m splits, it becomes two bacteria of mass m/2 each. For example, a bacterium of mass 3 can split into two bacteria of mass 1.5.

Also, every night, the mass of every bacteria will increase by one.

Phoenix is wondering if it is possible for the total mass of all the bacteria to be exactly n. If it is possible, he is interested in the way to obtain that mass using the minimum possible number of nights. Help him become the best scientist!

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains an integer n (2 ≤ n ≤ 10^9) — the sum of bacteria masses that Phoenix is interested in. 

Output

For each test case, if there is no way for the bacteria to exactly achieve total mass n, print -1. Otherwise, print two lines.

The first line should contain an integer d — the minimum number of nights needed.

The next line should contain d integers, with the i-th integer representing the number of bacteria that should split on the i-th day.

If there are multiple solutions, print any.

Example

Input


3
9
11
2


Output


3
1 0 2 
3
1 1 2
1
0 

Note

In the first test case, the following process results in bacteria with total mass 9: 

  * Day 1: The bacterium with mass 1 splits. There are now two bacteria with mass 0.5 each. 
  * Night 1: All bacteria's mass increases by one. There are now two bacteria with mass 1.5. 
  * Day 2: None split. 
  * Night 2: There are now two bacteria with mass 2.5. 
  * Day 3: Both bacteria split. There are now four bacteria with mass 1.25. 
  * Night 3: There are now four bacteria with mass 2.25. 

The total mass is 2.25+2.25+2.25+2.25=9. It can be proved that 3 is the minimum number of nights needed. There are also other ways to obtain total mass 9 in 3 nights.

 

In the second test case, the following process results in bacteria with total mass 11: 

  * Day 1: The bacterium with mass 1 splits. There are now two bacteria with mass 0.5. 
  * Night 1: There are now two bacteria with mass 1.5. 
  * Day 2: One bacterium splits. There are now three bacteria with masses 0.75, 0.75, and 1.5. 
  * Night 2: There are now three bacteria with masses 1.75, 1.75, and 2.5. 
  * Day 3: The bacteria with mass 1.75 and the bacteria with mass 2.5 split. There are now five bacteria with masses 0.875, 0.875, 1.25, 1.25, and 1.75. 
  * Night 3: There are now five bacteria with masses 1.875, 1.875, 2.25, 2.25, and 2.75. 

The total mass is 1.875+1.875+2.25+2.25+2.75=11. It can be proved that 3 is the minimum number of nights needed. There are also other ways to obtain total mass 11 in 3 nights.

 

In the third test case, the bacterium does not split on day 1, and then grows to mass 2 during night 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Quido and Hugo are making a chocolate cake. The central ingredient of the cake is a large chocolate bar, lying unwrapped on the kitchen table. The bar is an $M \times N$ rectangular grid of chocolate blocks. All of the $MN$ blocks are rectangles of identical shape and size. The chocolate bar is of top quality and the friends want to eat part of it, before the rest is used in the cake.

“OK,” says Quido, “let’s divide the whole bar into two triangular chunks by a straight diagonal cut from its upper-left corner to its lower-right corner. We will then eat all of the blocks which have been cut exactly in half, into two equal-area pieces. You will eat one half and I will eat the other half of each such block. All other blocks, that is, the blocks which are either uncut or cut into two parts of different sizes, will go directly into the cake. Of course, we will make sure the cut is perfectly precise.

Let’s see how much chocolate we get to eat!”

-----Input-----
The input consists of two space-separated integers $M$ and $N$ given on a single line, (where $1 \leq M, N \leq 10^{18}$). The numbers $M$ and $N$ denote the number of blocks in one column and in one row, respectively, in the chocolate bar.

-----Output-----
Print the number of blocks of the chocolate bar which are cut into exactly two pieces of equal area.

-----Examples-----
Sample Input:
6 10
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once a Mathematician was trapped by military people during a world war with his forty colleagues. The colleagues were without any weapons, only the mathematician had a knife. And with no weapons they were not able to fight with the military, so they decided to kill themselves rather than being killed by military.
They all decided that they will stand in a circle and the every third person will 
kill himself but the mathematician didn't like this idea and had no intention 
of killing himself. He calculates where should he stand so that he is the last one left. You have to tell the serial number of last man standing. 
Note:- Instead of every 3rd position it will be every 2nd position and of course the number of colleagues will be much more than 40.

Input:-
The first line of input is an integer N  that specifies the number of test cases. After that every line contains an integer X  which is the number of colleagues.

Output:-
For each test case generate a line containing the position of the colleague who survives. Assume that the colleagues have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2.

Constraints:-
1 ≤ N ≤ 1000
5 ≤ X ≤ 100000000

SAMPLE INPUT
4
5
11
45
23987443

SAMPLE OUTPUT
3
7
27
14420455

Explanation

Taking the case of the first test case if there are 5 participants in the circle, the first to go is 2, followed by 4, followed by 1, followed by 5 which leaves 3 at the end.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a rational number n

``` n >= 0, with denominator strictly positive```  

- as a string (example: "2/3" in Ruby, Python, Clojure, JS, CS, Go) 
- or as two strings (example: "2" "3" in Haskell, Java, CSharp, C++, Swift) 
- or as a rational or decimal number (example: 3/4, 0.67 in R) 
- or two integers (Fortran)

decompose 
this number as a sum of rationals with numerators equal to one and without repetitions
(2/3 = 1/2 + 1/6 is correct but not 2/3 = 1/3 + 1/3, 1/3 is repeated).
    
The algorithm must be "greedy", so at each stage the new rational obtained in the decomposition must have a denominator as small as possible. 
In this manner the sum of a few fractions in the decomposition gives a rather good approximation of the rational to decompose.
    
2/3 = 1/3 + 1/3 doesn't fit because of the repetition but also because the first 1/3 has a denominator bigger than the one in 1/2 
in the decomposition 2/3 = 1/2 + 1/6.
    
### Example: 
(You can see other examples in "Sample Tests:")
```
decompose("21/23") or "21" "23" or 21/23 should return 

["1/2", "1/3", "1/13", "1/359", "1/644046"] in Ruby, Python, Clojure, JS, CS, Haskell, Go

"[1/2, 1/3, 1/13, 1/359, 1/644046]" in Java, CSharp, C++

"1/2,1/3,1/13,1/359,1/644046" in C, Swift, R
```  

### Notes
1) The decomposition of 21/23 as
```
21/23 = 1/2 + 1/3 + 1/13 + 1/598 + 1/897
```
is exact but don't fulfill our requirement because 598 is bigger than 359.
Same for 
```
21/23 = 1/2 + 1/3 + 1/23 + 1/46 + 1/69 (23 is bigger than 13)
or 
21/23 = 1/2 + 1/3 + 1/15 + 1/110 + 1/253 (15 is bigger than 13).
```
    
2) The rational given to decompose could be greater than one or equal to one, in which case the first "fraction" will be an integer 
(with an implicit denominator of 1). 

3) If the numerator parses to zero the function "decompose" returns [] (or "".

4) The number could also be a decimal which can be expressed as a rational. 

examples:

`0.6` in Ruby, Python, Clojure,JS, CS, Julia, Go
  
`"66" "100"` in Haskell, Java, CSharp, C++, C, Swift, Scala, Kotlin

`0.67` in R.

**Ref:**
http://en.wikipedia.org/wiki/Egyptian_fraction

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N people, conveniently numbered 1 through N.
We want to divide them into some number of groups, under the following two conditions:
 - Every group contains between A and B people, inclusive.
 - Let F_i be the number of the groups containing exactly i people. Then, for all i, either F_i=0 or C≤F_i≤D holds.
Find the number of these ways to divide the people into groups.
Here, two ways to divide them into groups is considered different if and only if there exists two people such that they belong to the same group in exactly one of the two ways.
Since the number of these ways can be extremely large, print the count modulo 10^9+7.

-----Constraints-----
 - 1≤N≤10^3
 - 1≤A≤B≤N
 - 1≤C≤D≤N

-----Input-----
The input is given from Standard Input in the following format:
N A B C D

-----Output-----
Print the number of ways to divide the people into groups under the conditions, modulo 10^9+7.

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

-----Sample Output-----
4

There are four ways to divide the people:
 - (1,2),(3)
 - (1,3),(2)
 - (2,3),(1)
 - (1,2,3)
The following way to divide the people does not count: (1),(2),(3). This is because it only satisfies the first condition and not the second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Brandon Greg Jr. is an art enthusiast who covered the entirety of the walls of his room with works of art. Brandon’s room is in the shape of a simple polygon (simple means that the polygon does not intersect itself). If Brandon is at point $X$, then he can see all points $Y$ such that the line segment $XY$ (excluding point $Y$) does not intersect any walls. Since Brandon’s happiness is proportional to the amount of art he can see by turning his head, he wants to know the area of the set of points from where he could see all of the walls of his room (and thus see his entire art collection). You may assume that Brandon has a very flexible neck.

-----Input-----
The first line of input contains a single integer $n$ ($3\le n\le 2\cdot 10^5$), representing the number of vertices of Brandon’s room.

Each of the next $n$ lines of input contains two space-separated real numbers $x_ i$ and $y_ i$ ($|x_ i|, |y_ i| \le 10^5$), representing the cartesian coordinates of the $i$-th vertex of Brandon’s room. The coordinates have at most two digits after the decimal place. It is guaranteed that the polygon is simple. The vertices may be given in clockwise or counterclockwise order.

-----Output-----
Output the area of the set of points from where Brandon could see all of the walls of his room. The output will be considered correct if the absolute or relative error is within $10^{-4}$ of the answer (if $a$ is the output and $b$ is the answer, then $a$ will be considered correct if $\frac{|a-b|}{\max \{ 1,b\} } \le 10^{-4}$.

-----Examples-----
Sample Input 1:
5
2 0
1 1
0 2
-2 0
0 -2
Sample Output 1:
8.0000000000

Sample Input 2:
5
0.2 0.00
0 -0.2
0.0 0
-0.2 0
0 0.20
Sample Output 2:
0.0200000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arkady coordinates rounds on some not really famous competitive programming platform. Each round features $n$ problems of distinct difficulty, the difficulties are numbered from $1$ to $n$.

To hold a round Arkady needs $n$ new (not used previously) problems, one for each difficulty. As for now, Arkady creates all the problems himself, but unfortunately, he can't just create a problem of a desired difficulty. Instead, when he creates a problem, he evaluates its difficulty from $1$ to $n$ and puts it into the problems pool.

At each moment when Arkady can choose a set of $n$ new problems of distinct difficulties from the pool, he holds a round with these problems and removes them from the pool. Arkady always creates one problem at a time, so if he can hold a round after creating a problem, he immediately does it.

You are given a sequence of problems' difficulties in the order Arkady created them. For each problem, determine whether Arkady held the round right after creating this problem, or not. Initially the problems pool is empty.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of difficulty levels and the number of problems Arkady created.

The second line contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$) — the problems' difficulties in the order Arkady created them.


-----Output-----

Print a line containing $m$ digits. The $i$-th digit should be $1$ if Arkady held the round after creation of the $i$-th problem, and $0$ otherwise.


-----Examples-----
Input
3 11
2 3 1 2 2 2 3 2 2 3 1

Output
00100000001

Input
4 8
4 1 3 3 2 3 3 3

Output
00001000



-----Note-----

In the first example Arkady held the round after the first three problems, because they are of distinct difficulties, and then only after the last problem.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An elementary school class is going on a road trip by bus to a computer factory. However, the driver is really tired of having to drive fighting kids all day, so she suggested that the class should split up and go to the factory in groups. She has already observed which kids dislike each other and are likely to fight, so she wants to make sure they do not end up in the same group. Of course, driving everyone one-by-one is a waste of time and money, so the driver wants to minimize the number of groups she has to drive. In addition, the bus is pretty small, and may only fit up to $c$ kids at a time. 

You are to write a program which helps her with the task of making these groups. Given the number of kids and their enemies, find the minimum number of groups required, as well as a division of the class into this minimum number of groups

-----Input-----
The first line contains three integers $n$, $k$, and $c$ ($1 \le n \le 17$, $0 \le k \le \frac{n(n-1)}{2}$ and $1 \le c \le n$) – the number of kids, pairs of enemies, and the capacity of the bus, respectively. Then follow $n$ lines with the kids’ names. Each name consists solely of the characters A-Z and a-z, is non-empty, and at most $10$ characters long. Then follow $k$ lines, each containing a pair of space-separated names indicating a pair of kids that dislike each other. No pair of names appears twice, and no kid is their own enemy.

-----Output-----
On the first line, output the minimum number of groups, followed by one line per group containing the names of the children in that group (separated by spaces).

-----Examples-----
Sample Input:
2 0 1
Alice
Bob
Sample Output:
2
Alice
Bob

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Naman has two binary strings $s$ and $t$ of length $n$ (a binary string is a string which only consists of the characters "0" and "1"). He wants to convert $s$ into $t$ using the following operation as few times as possible.

In one operation, he can choose any subsequence of $s$ and rotate it clockwise once.

For example, if $s = 1\textbf{1}101\textbf{00}$, he can choose a subsequence corresponding to indices ($1$-based) $\{2, 6, 7 \}$ and rotate them clockwise. The resulting string would then be $s = 1\textbf{0}101\textbf{10}$.

A string $a$ is said to be a subsequence of string $b$ if $a$ can be obtained from $b$ by deleting some characters without changing the ordering of the remaining characters.

To perform a clockwise rotation on a sequence $c$ of size $k$ is to perform an operation which sets $c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$ simultaneously.

Determine the minimum number of operations Naman has to perform to convert $s$ into $t$ or say that it is impossible. 


-----Input-----

The first line contains a single integer $n$ $(1 \le n \le 10^6)$ — the length of the strings.

The second line contains the binary string $s$ of length $n$.

The third line contains the binary string $t$ of length $n$.


-----Output-----

If it is impossible to convert $s$ to $t$ after any number of operations, print $-1$.

Otherwise, print the minimum number of operations required.


-----Examples-----
Input
6
010000
000001

Output
1
Input
10
1111100000
0000011111

Output
5
Input
8
10101010
01010101

Output
1
Input
10
1111100000
1111100001

Output
-1


-----Note-----

In the first test, Naman can choose the subsequence corresponding to indices $\{2, 6\}$ and rotate it once to convert $s$ into $t$.

In the second test, he can rotate the subsequence corresponding to all indices $5$ times. It can be proved, that it is the minimum required number of operations.

In the last test, it is impossible to convert $s$ into $t$.

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