vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Little chandu is very fond of playing games. Recently, He found a few straws each of length 1 inches in the store room. He took all of them and decided to mark a rectangular area on the floor with straws and warn rest of the family members to not to enter that area so that he can play in peace. He wants to maximize that area. But, unable to do so, He seeks for your help. You being the elder brother of chandu, write a program for him to find maximum area that he can cover in inches using N straws.

Input:

First line of input contains an integer t. then, t lines follow each containing a single integer N - No of straws.

Output:

Print the area of largest rectangle that can be formed using the given sticks.

Constraints:

0 ≤ t ≤ 25000  

1 ≤ N ≤ 10^{10}  

SAMPLE INPUT
3
6
9
11

SAMPLE OUTPUT
2
4
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string A of length N.

You can perform the following type of operation on the string A:
Choose two different indices i and j (1≤ i,j≤ N);
Change A_{i} and A_{j} to A_{i} \oplus A_{j}. Here \oplus represents the [bitwise XOR] operation.

Find the minimum number of operations required to convert the given string into a [palindrome].

------ Input Format ------ 

- First line of the input contains T, the number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the size of the string.
- Second line of each test case contains a binary string A of length N containing 0s and 1s only.

------ Output Format ------ 

For each test case, print the minimum number of operations required to make the string a palindrome.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$ 1 ≤ N ≤ 2 \cdot 10^{5}$
- Sum of $N$ over all test cases does not exceeds $ 2 \cdot 10^{5} $.

----- Sample Input 1 ------ 
4
5
11011
7
0111010
1
1
4
1100
----- Sample Output 1 ------ 
0
1
0
1
----- explanation 1 ------ 
Test Case $1$ :  The given string $11011$ is already a palindrome. So, no operation is required. The answer for the case is $0$.

Test Case $2$ : The given string $0111010$ is not a palindrome. 
- Choose the indices $i=3$ and $j=5$. Now, $A_{3} \oplus A_{5} = 1\oplus 0 = 1$. Thus, we set $A_{3}$ and $A_{5}$ equal to $1$.

After the operation, the resulting string is $0111110$ which is a palindrome. The number of operations required is $1$.

Test Case $3$ :  The given string $1$ is already a palindrome. So, no operation is required. The answer for the case is $0$.

Test Case $4$ : The given string $1100$ is not a palindrome. 
- Choose the indices $i=1$ and $j=2$. Now, $A_{1} \oplus A_{2} = 1\oplus 1 = 0$. Thus, we set $A_{1}$ and $A_{2}$ equal to $0$.

After the operation, the resulting string is $0000$ which is a palindrome. The number of operations required is $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Permutation p is an ordered set of integers p_1,  p_2,  ...,  p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as p_{i}. We'll call number n the size or the length of permutation p_1,  p_2,  ...,  p_{n}.

We'll call position i (1 ≤ i ≤ n) in permutation p_1, p_2, ..., p_{n} good, if |p[i] - i| = 1. Count the number of permutations of size n with exactly k good positions. Print the answer modulo 1000000007 (10^9 + 7).


-----Input-----

The single line contains two space-separated integers n and k (1 ≤ n ≤ 1000, 0 ≤ k ≤ n).


-----Output-----

Print the number of permutations of length n with exactly k good positions modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
1 0

Output
1

Input
2 1

Output
0

Input
3 2

Output
4

Input
4 1

Output
6

Input
7 4

Output
328



-----Note-----

The only permutation of size 1 has 0 good positions.

Permutation (1, 2) has 0 good positions, and permutation (2, 1) has 2 positions.

Permutations of size 3:



 (1, 2, 3) — 0 positions

 $(1,3,2)$ — 2 positions

 $(2,1,3)$ — 2 positions

 $(2,3,1)$ — 2 positions

 $(3,1,2)$ — 2 positions

 (3, 2, 1) — 0 positions

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a robot named Micro in a matrix A, of integers of size N \times M, initially placed at the cell (X_1, Y_1). He has to rescue his princess Mini placed at cell  (X_2, Y_2). Rows are numbered from 1 to N and columns are numbered from 1 to M. He can move one step in either of the four directions: up, down, left and right. Also he can make a move if value at cell he is currently at is strictly less than the value at cell he is moving to. Help Micro find out if he can rescue his princess or not.

Input:
First line consists of T the number of test case.
In each test case first line consists of six space separated integers denoting N, M, X_1, Y_1, X_2, Y_2 . Then N lines follow each consisting of M space separated integers denoting the matrix.

Output:
For each test case, print in a new line, "YES" (without quotes) if Micro can rescue Mini otherwise print "NO" (without quotes).

Constraints:
 1≤ T ≤ 5
1 ≤ N, M  ≤ 10 
1 ≤ X_1, X_2  ≤ N  
1 ≤ Y_1, Y_2  ≤ M  
1 ≤ A[i][j] ≤ 100 

SAMPLE INPUT
2
2 2 1 1 2 2
2 1
1 3
3 3 1 1 2 3
2 1 1
3 2 7
4 5 6

SAMPLE OUTPUT
NO
YES

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string *s* written on the door consisting of characters '(', ')' and '#'. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each '#' with one or more ')' characters so that the final string becomes beautiful. 

Below there was also written that a string is called beautiful if for each *i* (1<=≤<=*i*<=≤<=|*s*|) there are no more ')' characters than '(' characters among the first *i* characters of *s* and also the total number of '(' characters is equal to the total number of ')' characters. 

Help Malek open the door by telling him for each '#' character how many ')' characters he must replace it with.

Input Specification:
The first line of the input contains a string *s* (1<=≤<=|*s*|<=≤<=105). Each character of this string is one of the characters '(', ')' or '#'. It is guaranteed that *s* contains at least one '#' character.

Output Specification:
If there is no way of replacing '#' characters which leads to a beautiful string print <=-<=1. Otherwise for each character '#' print a separate line containing a positive integer, the number of ')' characters this character must be replaced with.

If there are several possible answers, you may output any of them.

Demo Input:
['(((#)((#)\n', '()((#((#(#()\n', '#\n', '(#)\n']

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

Note:
|*s*| denotes the length of the string *s*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dasha logged into the system and began to solve problems. One of them is as follows:

Given two sequences a and b of length n each you need to write a sequence c of length n, the i-th element of which is calculated as follows: c_{i} = b_{i} - a_{i}.

About sequences a and b we know that their elements are in the range from l to r. More formally, elements satisfy the following conditions: l ≤ a_{i} ≤ r and l ≤ b_{i} ≤ r. About sequence c we know that all its elements are distinct.

 [Image] 

Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy. Due to an error in the test system only the sequence a and the compressed sequence of the sequence c were known from that test.

Let's give the definition to a compressed sequence. A compressed sequence of sequence c of length n is a sequence p of length n, so that p_{i} equals to the number of integers which are less than or equal to c_{i} in the sequence c. For example, for the sequence c = [250, 200, 300, 100, 50] the compressed sequence will be p = [4, 3, 5, 2, 1]. Pay attention that in c all integers are distinct. Consequently, the compressed sequence contains all integers from 1 to n inclusively.

Help Dasha to find any sequence b for which the calculated compressed sequence of sequence c is correct.


-----Input-----

The first line contains three integers n, l, r (1 ≤ n ≤ 10^5, 1 ≤ l ≤ r ≤ 10^9) — the length of the sequence and boundaries of the segment where the elements of sequences a and b are.

The next line contains n integers a_1,  a_2,  ...,  a_{n} (l ≤ a_{i} ≤ r) — the elements of the sequence a.

The next line contains n distinct integers p_1,  p_2,  ...,  p_{n} (1 ≤ p_{i} ≤ n) — the compressed sequence of the sequence c.


-----Output-----

If there is no the suitable sequence b, then in the only line print "-1".

Otherwise, in the only line print n integers — the elements of any suitable sequence b.


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

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

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

Output
-1



-----Note-----

Sequence b which was found in the second sample is suitable, because calculated sequence c = [2 - 3, 2 - 4, 2 - 8, 9 - 9] = [ - 1,  - 2,  - 6, 0] (note that c_{i} = b_{i} - a_{i}) has compressed sequence equals to p = [3, 2, 1, 4].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:   a ticket for one trip costs 20 byteland rubles,  a ticket for 90 minutes costs 50 byteland rubles,  a ticket for one day (1440 minutes) costs 120 byteland rubles. 

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.


-----Input-----

The first line of input contains integer number n (1 ≤ n ≤ 10^5) — the number of trips made by passenger.

Each of the following n lines contains the time of trip t_{i} (0 ≤ t_{i} ≤ 10^9), measured in minutes from the time of starting the system. All t_{i} are different, given in ascending order, i. e. t_{i} + 1 > t_{i} holds for all 1 ≤ i < n.


-----Output-----

Output n integers. For each trip, print the sum the passenger is charged after it.


-----Examples-----
Input
3
10
20
30

Output
20
20
10

Input
10
13
45
46
60
103
115
126
150
256
516

Output
20
20
10
0
20
0
0
20
20
10



-----Note-----

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tuple generator f^{(k)} = (f_1^{(k)}, f_2^{(k)}, ..., f_n^{(k)}), where f_i^{(k)} = (a_i ⋅ f_i^{(k - 1)} + b_i) mod p_i and f^{(0)} = (x_1, x_2, ..., x_n). Here x mod y denotes the remainder of x when divided by y. All p_i are primes.

One can see that with fixed sequences x_i, y_i, a_i the tuples f^{(k)} starting from some index will repeat tuples with smaller indices. Calculate the maximum number of different tuples (from all f^{(k)} for k ≥ 0) that can be produced by this generator, if x_i, a_i, b_i are integers in the range [0, p_i - 1] and can be chosen arbitrary. The answer can be large, so print the remainder it gives when divided by 10^9 + 7

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in the tuple.

The second line contains n space separated prime numbers — the modules p_1, p_2, …, p_n (2 ≤ p_i ≤ 2 ⋅ 10^6).

Output

Print one integer — the maximum number of different tuples modulo 10^9 + 7.

Examples

Input

4
2 3 5 7


Output

210


Input

3
5 3 3


Output

30

Note

In the first example we can choose next parameters: a = [1, 1, 1, 1], b = [1, 1, 1, 1], x = [0, 0, 0, 0], then f_i^{(k)} = k mod p_i.

In the second example we can choose next parameters: a = [1, 1, 2], b = [1, 1, 0], x = [0, 0, 1].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gorodetskiy is a university student. He is really good at math and really likes solving engaging math problems. In the last exam, his professor gave him really hard math problems to solve, but Gorodetskiy could not solve them and failed the exam, so the professor told him: "These problems are a piece of cake, you should know them from school!" Here is one of the problems from the exam - you can decide if it really was an easy problem or not.
You are given a positive integer $M$. Let's call a positive integer $A$ an interesting number if there is at least one integer $B$ ($A \le B$) such that $A \cdot B$ is divisible by $M$ and $\frac{A \cdot B}{M} = A+B$.
Find all interesting numbers. Let's denote the number of such integers by $K$; it is guaranteed that $K \le 3*10^5$.

-----Input-----
- The first line of the input contains a single 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 integer $M$.

-----Output-----
For each test case:
- First, print a line containing a single integer $K$.
- Then, print $K$ lines. For each valid $i$, the $i$-th of these lines should contain a single integer ― the $i$-th interesting number in increasing order.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le M \le 10^{14}$

-----Subtasks-----
Subtask #1 (20 points): $1 \le M \le 100$
Subtask #2 (20 points): $1 \le M \le 10^7$
Subtask #3 (60 points): original constraints

-----Example Input-----
2
3
6

-----Example Output-----
2
4
6
5
7
8
9
10
12

-----Explanation-----
Example case 1: There are two interesting numbers, $4$ and $6$. For $A = 4$, we can choose $B = 12$ and for $A = 6$, we can choose $B = 6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, count the numbers having an odd number of factors from 1 to N (inclusive).
 
Example 1:
Input:
N = 5
Output:
2
Explanation:
From 1 - 5 only 2 numbers,
1 and 4 are having odd number
of factors.
Example 2:
Input:
N = 1
Output:
1
Explanation:
1 have only 1(odd)
factor
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which takes an integer N as input parameters and returns an integer, the total count of numbers from 1 to N having an odd number of factors.
 
Expected Time Complexity: O(sqrt(N))
Expected Space Complexity: O(1)
 
Constraints:
0 <= N <= 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Given Length and Sum of Digits...

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have a positive integer *m* and a non-negative integer *s*. Your task is to find the smallest and the largest of the numbers that have length *m* and sum of digits *s*. The required numbers should be non-negative integers written in the decimal base without leading zeroes.

Input Specification:
The single line of the input contains a pair of integers *m*, *s* (1<=≤<=*m*<=≤<=100,<=0<=≤<=*s*<=≤<=900) — the length and the sum of the digits of the required numbers.

Output Specification:
In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1 -1" (without the quotes).

Demo Input:
['2 15\n', '3 0\n']

Demo Output:
['69 96\n', '-1 -1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A grasshopper is in a flower field. The field contains $N \cdot N$ flowers arranged in $N$ rows and $N$ columns. For each flower in the field, we know how many petals it has.

The grasshopper is initially on the flower in row $R$ and column $C$. Its goal is to visit as many flowers as possible while obeying these rules:
 - It can only jump into an adjacent row or column. If it jumps into the adjacent row, it must jump at least two columns, and if it jumps into the adjacent column, it must jump at least two rows. In other words, it can jump from flower $(r_1 , c_1)$ to flower $(r_2, c_2)$ if:
 - $|r_1 -r_2| = 1$ and $|c_1 -c_2 |> 1$ or
 - $|c_1 -c_2| = 1$ and $|r_1 -r_2 |> 1$
 - The number of petals on the next flower must be strictly larger than the number of petals on the previous flower.

Write a program that calculates the largest number of flowers the grasshopper can visit.

-----Input-----
The first line contains the integer $N$ ($1 \le N \le 1500$), the size of the field.

The second line contains integers $R$ ($1 \le R \le N$) and $C$ ($1 \le C \le N$), the grasshopper’s initial position.

The next $N$ lines contain $N$ positive integers separated by spaces, each at most $1000000$, the numbers of petals on the flowers.

-----Output-----
Output a single integer – the largest number of flowers the grasshopper can visit.

-----Examples-----
Sample Input:
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Normally, we decompose a number into binary digits by assigning it with powers of 2, with a coefficient of `0` or `1` for each term:

`25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1`

The choice of `0` and `1` is... not very binary. We shall perform the *true* binary expansion by expanding with powers of 2, but with a coefficient of `1` or `-1` instead:

`25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1`

Now *this* looks binary.

---

Given any positive number `n`, expand it using the true binary expansion, and return the result as an array, from the most significant digit to the least significant digit.

`true_binary(25) == [1,1,1,-1,-1]`

It should be trivial (the proofs are left as an exercise to the reader) to see that:

- Every odd number has infinitely many true binary expansions
- Every even number has no true binary expansions

Hence, `n` will always be an odd number, and you should return the *least* true binary expansion for any `n`.

Also, note that `n` can be very, very large, so your code should be very efficient.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
**This Kata is intended as a small challenge for my students**

All Star Code Challenge #29

Your friend Nhoj has dislexia, but can easily read messages if the words are written backwards.  
Create a function called `reverseSentence()/reverse_sentence()` that accepts a string argument. The function returns a string of the same length with each word reversed, but still in their original order.

```python
reverse_sentence("Hello !Nhoj Want to have lunch?") # "olleH johN! tnaW ot evah ?hcnul"
```
Note:  
A "word" should be considered a string split by a space character, " "
Letter capitalization should be maintained.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] consisting of n integers, find the length of the longest subarray with positive (non zero) product.
 
Example 1:
Input:
arr[] ={0, 1, -2, -3, -4} 
Output:
3
Explanation: 
The longest subarray with positive product is: 
{1, -2, -3}.Therefore, the required length is 3.
 
Example 2:
Input:
arr[]={-1, -2, 0, 1, 2}
Output:
2
Explanation:
The longest subarray with positive products 
are: {-1, -2}, {1, 2}. Therefore, the required 
length is 2.
 
Your Task: This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function maxLength() that takes array arr[], and an integer n as parameters and return the length of the longest subarray where the product of all of its element is positive. 
 
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
 
Constraints:
 1<=n<=10^{5}
-10^{9}<=arr[i]<=10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Mirko has been moving up in the world of basketball. He started as a mere spectator, but has already reached the coveted position of the national team coach!

 Mirco is now facing a difficult task: selecting five primary players for the upcoming match against Tajikistan. Since Mirko is incredibly lazy, he doesn't bother remembering players' names, let alone their actual skills. That's why he has settled on selecting five players who share the same first letter of their surnames, so that he can remember them easier. If there are no five players sharing the first letter of their surnames, Mirko will simply forfeit the game!

 Your task is to find the first letters Mirko's players' surnames can begin with(In alphabetical order), or return `"forfeit"` if Mirko can't gather a team.

# Input/Output


 - `[input]` string array `players`

  Array of players' surnames, consisting only of lowercase English letters.

 
 - `[output]` a string

  A **sorted** string of possible first letters, or "forfeit" if it's impossible to gather a team.


# Example

For `players = ["michael","jordan","lebron","james","kobe","bryant"]`, the output should be `"forfeit"`.

 For
 ```
 players = ["babic","keksic","boric","bukic",
              "sarmic","balic","kruzic","hrenovkic",
              "beslic","boksic","krafnic","pecivic",
              "klavirkovic","kukumaric","sunkic","kolacic",
              "kovacic","prijestolonasljednikovic"]
```
the output should be "bk".

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