vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The only difference between easy and hard versions is constraints.

A session has begun at Beland State University. Many students are taking exams.

Polygraph Poligrafovich is going to examine a group of $n$ students. Students will take the exam one-by-one in order from $1$-th to $n$-th. Rules of the exam are following:  The $i$-th student randomly chooses a ticket.  if this ticket is too hard to the student, he doesn't answer and goes home immediately (this process is so fast that it's considered no time elapses). This student fails the exam.  if the student finds the ticket easy, he spends exactly $t_i$ minutes to pass the exam. After it, he immediately gets a mark and goes home. 

Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student.

The duration of the whole exam for all students is $M$ minutes ($\max t_i \le M$), so students at the end of the list have a greater possibility to run out of time to pass the exam.

For each student $i$, you should count the minimum possible number of students who need to fail the exam so the $i$-th student has enough time to pass the exam.

For each student $i$, find the answer independently. That is, if when finding the answer for the student $i_1$ some student $j$ should leave, then while finding the answer for $i_2$ ($i_2>i_1$) the student $j$ student does not have to go home.


-----Input-----

The first line of the input contains two integers $n$ and $M$ ($1 \le n \le 100$, $1 \le M \le 100$) — the number of students and the total duration of the exam in minutes, respectively.

The second line of the input contains $n$ integers $t_i$ ($1 \le t_i \le 100$) — time in minutes that $i$-th student spends to answer to a ticket.

It's guaranteed that all values of $t_i$ are not greater than $M$.


-----Output-----

Print $n$ numbers: the $i$-th number must be equal to the minimum number of students who have to leave the exam in order to $i$-th student has enough time to pass the exam.


-----Examples-----
Input
7 15
1 2 3 4 5 6 7

Output
0 0 0 0 0 2 3 
Input
5 100
80 40 40 40 60

Output
0 1 1 2 3 


-----Note-----

The explanation for the example 1.

Please note that the sum of the first five exam times does not exceed $M=15$ (the sum is $1+2+3+4+5=15$). Thus, the first five students can pass the exam even if all the students before them also pass the exam. In other words, the first five numbers in the answer are $0$.

In order for the $6$-th student to pass the exam, it is necessary that at least $2$ students must fail it before (for example, the $3$-rd and $4$-th, then the $6$-th will finish its exam in $1+2+5+6=14$ minutes, which does not exceed $M$).

In order for the $7$-th student to pass the exam, it is necessary that at least $3$ students must fail it before (for example, the $2$-nd, $5$-th and $6$-th, then the $7$-th will finish its exam in $1+3+4+7=15$ minutes, which does not exceed $M$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Piegirl found the red button. You have one last chance to change the inevitable end.

The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once. 

Your task is to find any such order and print it. If there is no such order, print -1.


-----Input-----

Input consists of a single integer n (2 ≤ n ≤ 10^5).


-----Output-----

Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.


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

Output
0 1 0

Input
3

Output
-1
Input
4

Output
0 1 3 2 0

Input
16

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Golorps are mysterious creatures who feed on variables. Golorp's name is a program in some programming language. Some scientists believe that this language is Befunge; golorps are tantalizingly silent.

Variables consumed by golorps can take values from 0 to 9, inclusive. For each golorp its daily diet is defined by its name. Some golorps are so picky that they can't be fed at all. Besides, all golorps are very health-conscious and try to eat as little as possible. Given a choice of several valid sequences of variable values, each golorp will choose lexicographically smallest one.

For the purposes of this problem you can assume that a golorp consists of jaws and a stomach. The number of variables necessary to feed a golorp is defined by the shape of its jaws. Variables can get to the stomach only via the jaws.

A hungry golorp is visiting you. You know its name; feed it or figure out that it's impossible.


-----Input-----

The input is a single string (between 13 and 1024 characters long) — the name of the visiting golorp. All names are similar and will resemble the ones given in the samples. The name is guaranteed to be valid.


-----Output-----

Output lexicographically smallest sequence of variable values fit for feeding this golorp. Values should be listed in the order in which they get into the jaws. If the golorp is impossible to feed, output "false".


-----Examples-----
Input
?(_-_/___*__):-___>__.

Output
0010

Input
?(__-_+_/_____):-__>__,_____<__.

Output
false

Input
?(______________________/____+_______*__-_____*______-___):-__<___,___<____,____<_____,_____<______,______<_______.

Output
0250341

Input
?(__+___+__-___):-___>__.

Output
0101

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).
The returned string must have no leading zeroes, unless the string is "0".
 

Example 1:
Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2


Example 2:
Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3


Example 3:
Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4

 
Note:

0 <= N <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoebe and Joey are playing cards. They have N decks of cards.

Each deck of cards contain 52 cards:  
26 Red cards (2 Aces + 6 Faces + 18 Ranks)
26 Black cards (2 Aces + 6 Faces + 18 Ranks)

They have decided to play with M cards out of these N*52 cards. Phoebe asks  Joey to select M cards with following restrictions:  
Number of Red cards = Number of Black cards 
Number of Face cards = Number of Rank Cards 
There should not be any Ace card in the selected M cards 

Your task is to find the number of ways Joey can select M cards out of N*52 cards abiding the above restrictions.  

Since the answer can be very large, print it modulo 10^9 + 7

Input:

First line contains T - number of test cases.
Each of the next T lines contains two space separated integers, N - number of decks of cards and M - number of cards to be selected.  

Output:

Print the required result for each test case in new line.  

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 50
2 ≤ M ≤ 1000

Side Info: Faces are King, Queen and Jack. Ranks are cards numbered from 2 to 10.

SAMPLE INPUT
2
1 2
1 3

SAMPLE OUTPUT
216
0

Explanation

Test Case #1:
We have 1 deck of cards. We have to choose 2 cards. 
In 1 deck we have; 6 Red Face cards, 18 Red Rank cards, 6 Black Face cards and 18 Black Rank cards.
We must choose 1 Red and 1 Black card and at the same time one of them should be Face card and other should be Rank card. 
So, we select one from 6 Red Face cards and 1 from 18 Black Rank cards. This makes 618 = 108 ways.
Again, we can choose 1 from 18 Red Rank cards and 1 from 6 Black Face cards. This makes another 186 = 108 ways. Summing up gives 216.  

Test Case #2:
Here M is odd. So it is not possible to choose equal number of Red and Black cards. Hence th answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?

You can read about longest common subsequence there: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.


-----Output-----

Print the length of the longest common subsequence.


-----Examples-----
Input
4 3
1 4 2 3
4 1 2 3
1 2 4 3

Output
3



-----Note-----

The answer for the first test sample is subsequence [1, 2, 3].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
**Principal Diagonal** -- The principal diagonal in a matrix identifies those elements of the matrix running from North-West to South-East.

**Secondary Diagonal** -- the secondary diagonal of a matrix identifies those elements of the matrix running from North-East to South-West.

For example:
```
matrix:             [1, 2, 3]
                    [4, 5, 6]
                    [7, 8, 9]

principal diagonal: [1, 5, 9]
secondary diagonal: [3, 5, 7]

```

## Task
Your task is to find which diagonal is "larger": which diagonal has a bigger sum of their elements.

* If the principal diagonal is larger, return `"Principal Diagonal win!"`
* If the secondary diagonal is larger, return `"Secondary Diagonal win!"`
* If they are equal, return `"Draw!"`

**Note:** You will always receive matrices of the same dimension.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Masha and geometric depression

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression *b* defined by two integers *b*1 and *q*. Remind that a geometric progression is a sequence of integers *b*1,<=*b*2,<=*b*3,<=..., where for each *i*<=&gt;<=1 the respective term satisfies the condition *b**i*<==<=*b**i*<=-<=1·*q*, where *q* is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both *b*1 and *q* can equal 0. Also, Dvastan gave Masha *m* "bad" integers *a*1,<=*a*2,<=...,<=*a**m*, and an integer *l*.

Masha writes all progression terms one by one onto the board (including repetitive) while condition |*b**i*|<=≤<=*l* is satisfied (|*x*| means absolute value of *x*). There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board. In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print "inf" in case she needs to write infinitely many integers.

Input Specification:
The first line of input contains four integers *b*1, *q*, *l*, *m* (-109<=≤<=*b*1,<=*q*<=≤<=109, 1<=≤<=*l*<=≤<=109, 1<=≤<=*m*<=≤<=105) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of "bad" integers, respectively.

The second line contains *m* distinct integers *a*1,<=*a*2,<=...,<=*a**m* (-109<=≤<=*a**i*<=≤<=109) — numbers that will never be written on the board.

Output Specification:
Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or "inf" (without quotes) otherwise.

Demo Input:
['3 2 30 4\n6 14 25 48\n', '123 1 2143435 4\n123 11 -5453 141245\n', '123 1 2143435 4\n54343 -13 6 124\n']

Demo Output:
['3', '0', 'inf']

Note:
In the first sample case, Masha will write integers 3, 12, 24. Progression term 6 will be skipped because it is a "bad" integer. Terms bigger than 24 won't be written because they exceed *l* by absolute value.

In the second case, Masha won't write any number because all terms are equal 123 and this is a "bad" integer.

In the third case, Masha will write infinitely integers 123.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dexter, being irritated by DD, gave her a lucrative game to play to keep her busy.
There are $N$ bags numbered $1$ to $N$. The $i_{th}$ bag contains $A_i$ coins. The bags are placed in a circular order such that the $N_{th}$ bag is adjacent to the $1^{st}$ bag. 
DD can select $K$ consecutive adjacent bags and take all the coins in them.   Help her find the maximum number of coins she can take by making the ideal choice.
Note that the selected bags must be consecutive. Since they are placed in circular order, bag number $1$ and $N$ are considered to be consecutive.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- First-line contains $N$ and $K$.
- Second-line contains $N$ numbers $A_1, A_2,...,A_N$,  

-----Output:-----
For each test case, output in a single line, the maximum money that can be collected by DD.

-----Constraints-----
- $1 \leq T \leq 100$
- $5 \leq N \leq 10^5$
- $1 \leq K < N$
- $1 \leq A_i \leq 10^5$
Sum of $N$ over all test cases is less than $10^6$

-----Sample Input:-----
1
5 3
8 6 9 4 10

-----Sample Output:-----
24

-----EXPLANATION:-----
The ideal choice would be to take the last bag with $10$ coins and the first $2$ bags with $8$ and $6$ coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a time in AM/PM format as a string, convert it to military (24-hour) time as a string.

Midnight is 12:00:00AM on a 12-hour clock, and 00:00:00 on a 24-hour clock. Noon is 12:00:00PM on a 12-hour clock, and 12:00:00 on a 24-hour clock


Sample Input: 07:05:45PM
Sample Output: 19:05:45

Try not to use built in DateTime libraries.

For more information on military time, check the wiki https://en.wikipedia.org/wiki/24-hour_clock#Military_time

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are an integer N and arrays S, T, U, and V, each of length N. Construct an N×N matrix a that satisfy the following conditions:

* a_{i,j} is an integer.
* 0 \leq a_{i,j} \lt 2^{64}.
* If S_{i} = 0, the bitwise AND of the elements in the i-th row is U_{i}.
* If S_{i} = 1, the bitwise OR of the elements in the i-th row is U_{i}.
* If T_{i} = 0, the bitwise AND of the elements in the i-th column is V_{i}.
* If T_{i} = 1, the bitwise OR of the elements in the i-th column is V_{i}.



However, there may be cases where no matrix satisfies the conditions.

Constraints

* All values in input are integers.
* 1 \leq N \leq 500
* 0 \leq S_{i} \leq 1
* 0 \leq T_{i} \leq 1
* 0 \leq U_{i} \lt 2^{64}
* 0 \leq V_{i} \lt 2^{64}

Input

Input is given from Standard Input in the following format:


N
S_{1} S_{2} ...  S_{N}
T_{1} T_{2} ...  T_{N}
U_{1} U_{2} ...  U_{N}
V_{1} V_{2} ...  V_{N}


Output

If there exists a matrix that satisfies the conditions, print one such matrix in the following format:


a_{1,1} ...  a_{1,N}
:
a_{N,1} ...  a_{N,N}


Note that any matrix satisfying the conditions is accepted.

If no matrix satisfies the conditions, print -1.

Examples

Input

2
0 1
1 0
1 1
1 0


Output

1 1
1 0


Input

2
1 1
1 0
15 15
15 11


Output

15 11
15 11

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Petya was solving a very interesting problem. But although he used many optimization techniques, his solution still got Time limit exceeded verdict. Petya conducted a thorough analysis of his program and found out that his function for finding maximum element in an array of *n* positive integers was too slow. Desperate, Petya decided to use a somewhat unexpected optimization using parameter *k*, so now his function contains the following code:

That way the function iteratively checks array elements, storing the intermediate maximum, and if after *k* consecutive iterations that maximum has not changed, it is returned as the answer.

Now Petya is interested in fault rate of his function. He asked you to find the number of permutations of integers from 1 to *n* such that the return value of his function on those permutations is not equal to *n*. Since this number could be very big, output the answer modulo 109<=+<=7.

Input Specification:
The only line contains two integers *n* and *k* (1<=≤<=*n*,<=*k*<=≤<=106), separated by a space — the length of the permutations and the parameter *k*.

Output Specification:
Output the answer to the problem modulo 109<=+<=7.

Demo Input:
['5 2\n', '5 3\n', '6 3\n']

Demo Output:
['22\n', '6\n', '84\n']

Note:
Permutations from second example: 

[4, 1, 2, 3, 5], [4, 1, 3, 2, 5], [4, 2, 1, 3, 5], [4, 2, 3, 1, 5], [4, 3, 1, 2, 5], [4, 3, 2, 1, 5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem you will be given a range 'n', and you are supposed to find all composite numbers within that range. Make your program efficient as time limit of the program is set to 1 second. Choose an efficient algorithm to find all the composite numbers within the range 0 to n.

Input

n - a single positive Integer.

Output

Space separated composite-numbers within the range of 0 and n.

Constrains

1 ≤ n ≤ 10000

SAMPLE INPUT
8

SAMPLE OUTPUT
4 6 8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The employees of the F company have lots of ways to entertain themselves. Today they invited a famous magician who shows a trick with plastic cups and a marble.

The point is to trick the spectator's attention. Initially, the spectator stands in front of a line of *n* plastic cups. Then the magician places a small marble under one cup and shuffles the cups. Then the spectator should guess which cup hides the marble.

But the head coder of the F company isn't easy to trick. When he saw the performance, he noticed several important facts:
 -  each cup contains a mark — a number from 1 to *n*; all marks on the cups are distinct; -  the magician shuffles the cups in *m* operations, each operation looks like that: take a cup marked *x**i*, sitting at position *y**i* in the row of cups (the positions are numbered from left to right, starting from 1) and shift it to the very beginning of the cup row (on the first position). 
When the head coder came home after work he wanted to re-do the trick. Unfortunately, he didn't remember the starting or the final position of the cups. He only remembered which operations the magician performed. Help the coder: given the operations in the order they were made find at least one initial permutation of the cups that can go through the described operations in the given order. Otherwise, state that such permutation doesn't exist.

Input Specification:
The first line contains integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=106). Each of the next *m* lines contains a couple of integers. The *i*-th line contains integers *x**i*, *y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=*n*) — the description of the *i*-th operation of the magician. Note that the operations are given in the order in which the magician made them and the coder wants to make them in the same order.

Output Specification:
If the described permutation doesn't exist (the programmer remembered wrong operations), print -1. Otherwise, print *n* distinct integers, each from 1 to *n*: the *i*-th number should represent the mark on the cup that initially is in the row in position *i*.

If there are multiple correct answers, you should print the lexicographically minimum one.

Demo Input:
['2 1\n2 1\n', '3 2\n1 2\n1 1\n', '3 3\n1 3\n2 3\n1 3\n']

Demo Output:
['2 1 \n', '2 1 3 \n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pupils Alice and Ibragim are best friends. It's Ibragim's birthday soon, so Alice decided to gift him a new puzzle. The puzzle can be represented as a matrix with $2$ rows and $n$ columns, every element of which is either $0$ or $1$. In one move you can swap two values in neighboring cells.

More formally, let's number rows $1$ to $2$ from top to bottom, and columns $1$ to $n$ from left to right. Also, let's denote a cell in row $x$ and column $y$ as $(x, y)$. We consider cells $(x_1, y_1)$ and $(x_2, y_2)$ neighboring if $|x_1 - x_2| + |y_1 - y_2| = 1$.

Alice doesn't like the way in which the cells are currently arranged, so she came up with her own arrangement, with which she wants to gift the puzzle to Ibragim. Since you are her smartest friend, she asked you to help her find the minimal possible number of operations in which she can get the desired arrangement. Find this number, or determine that it's not possible to get the new arrangement.


-----Input-----

The first line contains an integer $n$ ($1 \leq n \leq 200000$) — the number of columns in the puzzle.

Following two lines describe the current arrangement on the puzzle. Each line contains $n$ integers, every one of which is either $0$ or $1$.

The last two lines describe Alice's desired arrangement in the same format.


-----Output-----

If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print $-1$.


-----Examples-----

Input
5
0 1 0 1 0
1 1 0 0 1
1 0 1 0 1
0 0 1 1 0
Output
5
Input
3
1 0 0
0 0 0
0 0 0
0 0 0
Output
-1


-----Note-----

In the first example the following sequence of swaps will suffice:

$(2, 1), (1, 1)$,

$(1, 2), (1, 3)$,

$(2, 2), (2, 3)$,

$(1, 4), (1, 5)$,

$(2, 5), (2, 4)$.

It can be shown that $5$ is the minimal possible answer in this case.

In the second example no matter what swaps you do, you won't get the desired arrangement, so the answer is $-1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
To make one bouquet we need K adjacent flowers from the garden. Here the garden consists of N different flowers, the ith flower will bloom in the bloomDay[i]. Each flower can be used inside only one bouquets. We have to find the minimum number of days need to wait to make M bouquets from the garden. If we cannot make m bouquets, then return -1.
The first line of input contains two integers M and K.
The second line contains N space-separated integers of bloomDay[i] array.
Example 1:
Input:
M = 2, K = 3
bloomDay = [5, 5, 5, 5, 10, 5, 5]
Output:
10
Explanation:
As we need 2 (M = 2) bouquets and each should have 3 flowers,
After day 5: [x, x, x, x, _, x, x], we can make one bouquet of
the first three flowers that bloomed, but cannot make another bouquet.
After day 10: [x, x, x, x, x, x, x], Now we can make two bouquets,
taking 3 adjacent flowers in one bouquet.
Example 2:
Input: 
M = 3, K = 2
bloomDay = [1, 10, 3, 10, 2]
Output: 
-1
Explanation:
As 3 bouquets each having 2 flowers are needed, that means we need 6 flowers. 
But there are only 5 flowers so it is impossible to get the needed bouquets
therefore -1 will be returned.
Your Task:
Complete the function int solve(), which takes integer M, K, and a list of N integers as input and returns the  minimum number of days needed to wait to be able to make M bouquets from the garden.
 
Expected Time Complexity: O(N.log(maxVal)), where maxVal = max(bloomDay)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= M <= 10^{5}
1 <= K <= N
1 <= bloomDay[i] <= 10^{9}

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