vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an array arr[] of N integers arranged in a circular fashion. Your task is to find the maximum contiguous subarray sum.
Example 1:
Input:
N = 7
arr[] = {8,-8,9,-9,10,-11,12}
Output:
22
Explanation:
Starting from the last element
of the array, i.e, 12, and 
moving in a circular fashion, we 
have max subarray as 12, 8, -8, 9, 
-9, 10, which gives maximum sum 
as 22.
Example 2:
Input:
N = 8
arr[] = {10,-3,-4,7,6,5,-4,-1}
Output:
23
Explanation: Sum of the circular 
subarray with maximum sum is 23
Your Task:
The task is to complete the function circularSubarraySum() which returns a sum of the circular subarray with maximum sum.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{6}
-10^{6 }<= Arr[i] <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After passing a test, Vasya got himself a box of $n$ candies. He decided to eat an equal amount of candies each morning until there are no more candies. However, Petya also noticed the box and decided to get some candies for himself.

This means the process of eating candies is the following: in the beginning Vasya chooses a single integer $k$, same for all days. After that, in the morning he eats $k$ candies from the box (if there are less than $k$ candies in the box, he eats them all), then in the evening Petya eats $10\%$ of the candies remaining in the box. If there are still candies left in the box, the process repeats — next day Vasya eats $k$ candies again, and Petya — $10\%$ of the candies left in a box, and so on.

If the amount of candies in the box is not divisible by $10$, Petya rounds the amount he takes from the box down. For example, if there were $97$ candies in the box, Petya would eat only $9$ of them. In particular, if there are less than $10$ candies in a box, Petya won't eat any at all.

Your task is to find out the minimal amount of $k$ that can be chosen by Vasya so that he would eat at least half of the $n$ candies he initially got. Note that the number $k$ must be integer.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^{18}$) — the initial amount of candies in the box.


-----Output-----

Output a single integer — the minimal amount of $k$ that would allow Vasya to eat at least half of candies he got.


-----Example-----
Input
68

Output
3



-----Note-----

In the sample, the amount of candies, with $k=3$, would change in the following way (Vasya eats first):

$68 \to 65 \to 59 \to 56 \to 51 \to 48 \to 44 \to 41 \\ \to 37 \to 34 \to 31 \to 28 \to 26 \to 23 \to 21 \to 18 \to 17 \to 14 \\ \to 13 \to 10 \to 9 \to 6 \to 6 \to 3 \to 3 \to 0$.

In total, Vasya would eat $39$ candies, while Petya — $29$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of integers from 1 to N. Count the interesting pairs of (A, B) that satisfy the following conditions:

A and B are both subsets of the given set.
XOR(A) ≤ XOR(B)
A and B have no common elements.
XOR(A) is the bit-xor (^ in C++ and Java) results over all its elements (e.g. XOR({1, 3}) = 2). We define the XOR of an empty set to be 0 (XOR({}) = 0).

Note: The answer may be large so you only need to print its remainder by dividing with M.

Input Format

The first line contains two space-separated integers, N and M.

Constraints

In 20% test cases: 1 ≤ N ≤ 10 
In 50% test cases: 1 ≤ N ≤ 100 M=109+7 
In 100% test cases: 1 ≤ N ≤ 3000 1 ≤ M ≤ 109+7
Output Format

Print the answer on a single line.

SAMPLE INPUT
2 10

SAMPLE OUTPUT
5

Explanation

If A = {}, B could be {}, {1}, {2}, and {1, 2}. 
If A = {1}, B could be {2}. 
If A = {2}, there is no valid B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Near the great desert of Byteland lies a technologically advanced kingdom of hamsters. In the year 2020, to protect better their territories, the hamsters have decided to build a great wall surrounding crucial parts of their kingdom.

The kingdom of hamsters is represented by a convex polygon with $n$ vertices. Vertices are numbered from $1$ to $n$, either in clockwise or counter-clockwise order. The $i$-th vertex’s coordinate is $(x_ i, y_ i)$. The hamsters want to choose $6$ unique vertices (among the $n$ vertices) and build a convex hexagonal wall connecting these $6$ vertices. Furthermore, the hamsters want their wall to be as long as possible. In other words, the hexagonal wall should have largest circumference.

The hamsters want to know, for each vertex of their kingdom, if they choose this vertex as one of the vertices of the hexagonal wall (along with $5$ other vertices), what is the longest wall they can build?

Even though the hamsters are technologically advanced, their computers crashed when they executed a brute force code for this problem. Please help them!

-----Input-----
 - The first line of the input contains a single integer $n$ $(6 \le n \le 2000)$.
 - In the next $n$ lines, the $i$-th line contains two integers $x_ i$ and $y_ i$$(-10^9 \leq x_ i, y_ i \leq 10^9)$.

-----Output-----
Print exactly $n$ lines, the $i$-th line contains the maximum circumference of the convex hexagonal wall, such that the hexagon has the $i$-th vertex.

Your answer will be considered correct if its relative or absolute error doesn’t exceed $10^{-3}$.

Namely: let’s assume that your answer is $a$, and the answer of the jury is $b$. The checker program will consider your answer correct, if $\frac{|a-b|}{max(1,b)} \leq 10^{-3}$.

-----Explanation of the sample input-----
The left figure shows the first sample. There is only one way to create a convex hexagon. Its circumference is $2 + 4 \cdot \sqrt{2}$.

The right figure shows the second sample. The hexagon with the maximum circumference containing the first vertex is shown below. Its circumference is $6 + 2 \cdot \sqrt{29} + 4 \cdot \sqrt{2}$. Due to the symmetry of the polygon, the hexagons with the maximum circumference containing other vertices should have the same result.

-----Examples-----
Sample Input:
6
1 2
1 3
2 4
3 3
3 2
2 1
Sample Output:
7.656854249492381
7.656854249492381
7.656854249492381
7.656854249492381
7.656854249492381
7.656854249492381

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andre has very specific tastes. Recently he started falling in love with arrays.

Andre calls an nonempty array $b$ good, if sum of its elements is divisible by the length of this array. For example, array $[2, 3, 1]$ is good, as sum of its elements — $6$ — is divisible by $3$, but array $[1, 1, 2, 3]$ isn't good, as $7$ isn't divisible by $4$. 

Andre calls an array $a$ of length $n$ perfect if the following conditions hold:   Every nonempty subarray of this array is good.  For every $i$ ($1 \le i \le n$), $1 \leq a_i \leq 100$. 

Given a positive integer $n$, output any perfect array of length $n$. We can show that for the given constraints such an array always exists.

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first and only line of every test case contains a single integer $n$ ($1 \le n \le 100$).


-----Output-----

For every test, output any perfect array of length $n$ on a separate line. 


-----Example-----
Input
3
1
2
4

Output
24
19 33
7 37 79 49



-----Note-----

Array $[19, 33]$ is perfect as all $3$ its subarrays: $[19]$, $[33]$, $[19, 33]$, have sums divisible by their lengths, and therefore are good.

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

The inner tool returns the inner product of two arrays.

import numpy

A = numpy.array([0, 1])
B = numpy.array([3, 4])

print numpy.inner(A, B)     #Output : 4

outer    

The outer tool returns the outer product of two arrays.

import numpy

A = numpy.array([0, 1])
B = numpy.array([3, 4])

print numpy.outer(A, B)     #Output : [[0 0]
                            #          [3 4]]

Task  

You are given two arrays: $\mbox{A}$ and $\mbox{B}$. 

Your task is to compute their inner and outer product.

Input Format

The first line contains the space separated elements of array $\mbox{A}$. 

The second line contains the space separated elements of array $\mbox{B}$.

Output Format

First, print the inner product. 

Second, print the outer product.

Sample Input
0 1
2 3

Sample Output
3
[[0 0]
 [2 3]]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kejal have N points, with coordinates (1, 0), (2, 0), ..., (N, 0). Every point has a color, point with coordinate (i, 0) has color C[i].

Kejal have painted arcs between every pair of points with same color. Formally Kejal painted arc between points (i, 0) and (j, 0) if C[i] = C[j] and i != j, such arc has color C[i]. All the arcs are painted such way that they will reside along the positive quadrant.

Now Kejal wants to know how many pairs of arc with different color intersect?

INPUT

First line contain integer N. Next line contain integers C[1], C[2], ..., C[N].

OUTPUT

In single line output answer modulo 1000000007 (10^9 + 7).

CONSTRAINTS
1 ≤ N ≤ 100000
1 ≤ C[i] ≤ 100000

SAMPLE INPUT
6
1 2 1 2 1 2

SAMPLE OUTPUT
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function name `nextPerfectSquare` that returns the first perfect square that is greater than its integer argument. A `perfect square` is a integer that is equal to some integer squared. For example 16 is a perfect square because `16=4*4`. 
```
example

n   next perfect sqare

6    9
36   49 
0    1
-5   0 
```
```if-not:csharp
caution! the largest number tested is closer to `Number.MAX_SAFE_INTEGER`
```
```if:csharp
Caution! The largest number test is close to `Int64.MaxValue`
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k,  a_i = a_{k+1 - i}.

 
Example 1:
Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:
Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:
Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:
Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

 
Constraints:

text consists only of lowercase English characters.
1 <= text.length <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
SKITians are good with mensuration hence they like to play with geometric shapes like rectangles in the plane. You are given two rectangles as expected. The sides of each rectangle are parallel to the coordinate axes. Each rectangle is given by the coordinates of its lower left corner and its upper right corner. 

You are given the (x,y) coordinates for both of the corners.

You are required to find out the following properties of the rectangles. There are four options:

If the rectangles have a non-zero area in common, then print "Rectangle"
Otherwise, if they have a common line segment with non-zero length, print "Line"
Otherwise, if they have a point in common, print "Point"
Otherwise, print "Apart" (in all four cases, the quotes are just for clarity and the output is case sensitive).

Input

First line of input contains an integer T that denotes the number of test cases.

Each test case contains two lines of input where both lines have four space separated integers representing x1 y1 x2 y2.
First line is for first rectangle and second line of input for second rectangle.

Output

Print appropriate response in a line for each test case.

Constraint
1 ≤ T ≤ 200
0 ≤ x1,y1,x2,y2 ≤ 1000

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

SAMPLE OUTPUT
Line
Point
Apart

Explanation

Case #1:

As it is clear these two rectangles share a common line segment of length greater than zero.

Case #2:

In this case, both of rectangles only share a common point.

Case #3:

These two rectangles do not have anything common between then, hence they are "Apart" from each other.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kamil likes streaming the competitive programming videos. His MeTube channel has recently reached $100$ million subscribers. In order to celebrate this, he posted a video with an interesting problem he couldn't solve yet. Can you help him?

You're given a tree — a connected undirected graph consisting of $n$ vertices connected by $n - 1$ edges. The tree is rooted at vertex $1$. A vertex $u$ is called an ancestor of $v$ if it lies on the shortest path between the root and $v$. In particular, a vertex is an ancestor of itself.

Each vertex $v$ is assigned its beauty $x_v$ — a non-negative integer not larger than $10^{12}$. This allows us to define the beauty of a path. Let $u$ be an ancestor of $v$. Then we define the beauty $f(u, v)$ as the greatest common divisor of the beauties of all vertices on the shortest path between $u$ and $v$. Formally, if $u=t_1, t_2, t_3, \dots, t_k=v$ are the vertices on the shortest path between $u$ and $v$, then $f(u, v) = \gcd(x_{t_1}, x_{t_2}, \dots, x_{t_k})$. Here, $\gcd$ denotes the greatest common divisor of a set of numbers. In particular, $f(u, u) = \gcd(x_u) = x_u$.

Your task is to find the sum

$$ \sum_{u\text{ is an ancestor of }v} f(u, v). $$

As the result might be too large, please output it modulo $10^9 + 7$.

Note that for each $y$, $\gcd(0, y) = \gcd(y, 0) = y$. In particular, $\gcd(0, 0) = 0$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 100\,000$) — the number of vertices in the tree.

The following line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^{12}$). The value $x_v$ denotes the beauty of vertex $v$.

The following $n - 1$ lines describe the edges of the tree. Each of them contains two integers $a, b$ ($1 \le a, b \le n$, $a \neq b$) — the vertices connected by a single edge.


-----Output-----

Output the sum of the beauties on all paths $(u, v)$ such that $u$ is ancestor of $v$. This sum should be printed modulo $10^9 + 7$.


-----Examples-----
Input
5
4 5 6 0 8
1 2
1 3
1 4
4 5

Output
42

Input
7
0 2 3 0 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

Output
30



-----Note-----

The following figure shows all $10$ possible paths for which one endpoint is an ancestor of another endpoint. The sum of beauties of all these paths is equal to $42$: [Image]

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In the Bus of Characters there are $n$ rows of seat, each having $2$ seats. The width of both seats in the $i$-th row is $w_i$ centimeters. All integers $w_i$ are distinct.

Initially the bus is empty. On each of $2n$ stops one passenger enters the bus. There are two types of passengers: 
 -  an introvert always chooses a row where both seats are empty. Among these rows he chooses the one with the smallest seats width and takes one of the seats in it; -  an extrovert always chooses a row where exactly one seat is occupied (by an introvert). Among these rows he chooses the one with the largest seats width and takes the vacant place in it. 
You are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.

Input Specification:
The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of rows in the bus.

The second line contains the sequence of integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^{9}$), where $w_i$ is the width of each of the seats in the $i$-th row. It is guaranteed that all $w_i$ are distinct.

The third line contains a string of length $2n$, consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the $j$-th character is '0', then the passenger that enters the bus on the $j$-th stop is an introvert. If the $j$-th character is '1', the the passenger that enters the bus on the $j$-th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal $n$), and for each extrovert there always is a suitable row.

Output Specification:
Print $2n$ integers — the rows the passengers will take. The order of passengers should be the same as in input.

Demo Input:
['2\n3 1\n0011\n', '6\n10 8 9 11 13 5\n010010011101\n']

Demo Output:
['2 1 1 2 \n', '6 6 2 3 3 1 4 4 1 2 5 5 \n']

Note:
In the first example the first passenger (introvert) chooses the row $2$, because it has the seats with smallest width. The second passenger (introvert) chooses the row $1$, because it is the only empty row now. The third passenger (extrovert) chooses the row $1$, because it has exactly one occupied seat and the seat width is the largest among such rows. The fourth passenger (extrovert) chooses the row $2$, because it is the only row with an empty place.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You desperately need to build some string t. For that you've got n more strings s_1, s_2, ..., s_{n}. To build string t, you are allowed to perform exactly |t| (|t| is the length of string t) operations on these strings. Each operation looks like that:  choose any non-empty string from strings s_1, s_2, ..., s_{n};  choose an arbitrary character from the chosen string and write it on a piece of paper;  remove the chosen character from the chosen string. 

Note that after you perform the described operation, the total number of characters in strings s_1, s_2, ..., s_{n} decreases by 1. We are assumed to build string t, if the characters, written on the piece of paper, in the order of performed operations form string t.

There are other limitations, though. For each string s_{i} you know number a_{i} — the maximum number of characters you are allowed to delete from string s_{i}. You also know that each operation that results in deleting a character from string s_{i}, costs i rubles. That is, an operation on string s_1 is the cheapest (it costs 1 ruble), and the operation on string s_{n} is the most expensive one (it costs n rubles).

Your task is to count the minimum amount of money (in rubles) you will need to build string t by the given rules. Consider the cost of building string t to be the sum of prices of the operations you use.


-----Input-----

The first line of the input contains string t — the string that you need to build.

The second line contains a single integer n (1 ≤ n ≤ 100) — the number of strings to which you are allowed to apply the described operation. Each of the next n lines contains a string and an integer. The i-th line contains space-separated string s_{i} and integer a_{i} (0 ≤ a_{i} ≤ 100). Number a_{i} represents the maximum number of characters that can be deleted from string s_{i}.

All strings in the input only consist of lowercase English letters. All strings are non-empty. The lengths of all strings do not exceed 100 characters.


-----Output-----

Print a single number — the minimum money (in rubles) you need in order to build string t. If there is no solution, print -1.


-----Examples-----
Input
bbaze
3
bzb 2
aeb 3
ba 10

Output
8

Input
abacaba
4
aba 2
bcc 1
caa 2
bbb 5

Output
18

Input
xyz
4
axx 8
za 1
efg 4
t 1

Output
-1



-----Note-----

Notes to the samples:

In the first sample from the first string you should take characters "b" and "z" with price 1 ruble, from the second string characters "a", "e" и "b" with price 2 rubles. The price of the string t in this case is 2·1 + 3·2 = 8.

In the second sample from the first string you should take two characters "a" with price 1 ruble, from the second string character "c" with price 2 rubles, from the third string two characters "a" with price 3 rubles, from the fourth string two characters "b" with price 4 rubles. The price of the string t in this case is 2·1 + 1·2 + 2·3 + 2·4 = 18.

In the third sample the solution doesn't exist because there is no character "y" in given strings.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya has a scales for weighing loads and weights of masses w^0, w^1, w^2, ..., w^100 grams where w is some integer not less than 2 (exactly one weight of each nominal value). Vanya wonders whether he can weight an item with mass m using the given weights, if the weights can be put on both pans of the scales. Formally speaking, your task is to determine whether it is possible to place an item of mass m and some weights on the left pan of the scales, and some weights on the right pan of the scales so that the pans of the scales were in balance.


-----Input-----

The first line contains two integers w, m (2 ≤ w ≤ 10^9, 1 ≤ m ≤ 10^9) — the number defining the masses of the weights and the mass of the item.


-----Output-----

Print word 'YES' if the item can be weighted and 'NO' if it cannot.


-----Examples-----
Input
3 7

Output
YES

Input
100 99

Output
YES

Input
100 50

Output
NO



-----Note-----

Note to the first sample test. One pan can have an item of mass 7 and a weight of mass 3, and the second pan can have two weights of masses 9 and 1, correspondingly. Then 7 + 3 = 9 + 1.

Note to the second sample test. One pan of the scales can have an item of mass 99 and the weight of mass 1, and the second pan can have the weight of mass 100.

Note to the third sample test. It is impossible to measure the weight of the item in the manner described in the input.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Petya is learning to play chess. He has already learned how to move a king, a rook and a bishop. Let us remind you the rules of moving chess pieces. A chessboard is 64 square fields organized into an 8 × 8 table. A field is represented by a pair of integers (r, c) — the number of the row and the number of the column (in a classical game the columns are traditionally indexed by letters). Each chess piece takes up exactly one field. To make a move is to move a chess piece, the pieces move by the following rules:  A rook moves any number of fields horizontally or vertically.  A bishop moves any number of fields diagonally.  A king moves one field in any direction — horizontally, vertically or diagonally.  [Image] The pieces move like that 

Petya is thinking about the following problem: what minimum number of moves is needed for each of these pieces to move from field (r_1, c_1) to field (r_2, c_2)? At that, we assume that there are no more pieces besides this one on the board. Help him solve this problem.


-----Input-----

The input contains four integers r_1, c_1, r_2, c_2 (1 ≤ r_1, c_1, r_2, c_2 ≤ 8) — the coordinates of the starting and the final field. The starting field doesn't coincide with the final one.

You can assume that the chessboard rows are numbered from top to bottom 1 through 8, and the columns are numbered from left to right 1 through 8.


-----Output-----

Print three space-separated integers: the minimum number of moves the rook, the bishop and the king (in this order) is needed to move from field (r_1, c_1) to field (r_2, c_2). If a piece cannot make such a move, print a 0 instead of the corresponding number.


-----Examples-----
Input
4 3 1 6

Output
2 1 3

Input
5 5 5 6

Output
1 0 1

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