vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Diplomas and Certificates

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* students who have taken part in an olympiad. Now it's time to award the students.

Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Students with diplomas and certificates are called winners. But there are some rules of counting the number of diplomas and certificates. The number of certificates must be exactly *k* times greater than the number of diplomas. The number of winners must not be greater than half of the number of all students (i.e. not be greater than half of *n*). It's possible that there are no winners.

You have to identify the maximum possible number of winners, according to these rules. Also for this case you have to calculate the number of students with diplomas, the number of students with certificates and the number of students who are not winners.

Input Specification:
The first (and the only) line of input contains two integers *n* and *k* (1<=≤<=*n*,<=*k*<=≤<=1012), where *n* is the number of students and *k* is the ratio between the number of certificates and the number of diplomas.

Output Specification:
Output three numbers: the number of students with diplomas, the number of students with certificates and the number of students who are not winners in case when the number of winners is maximum possible.

It's possible that there are no winners.

Demo Input:
['18 2\n', '9 10\n', '1000000000000 5\n', '1000000000000 499999999999\n']

Demo Output:
['3 6 9\n', '0 0 9\n', '83333333333 416666666665 500000000002\n', '1 499999999999 500000000000\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Permutation *p* is an ordered set of integers *p*1,<=<=<=*p*2,<=<=<=...,<=<=<=*p**n*, consisting of *n* distinct positive integers not larger than *n*. We'll denote as *n* the length of permutation *p*1,<=<=<=*p*2,<=<=<=...,<=<=<=*p**n*.

Your task is to find such permutation *p* of length *n*, that the group of numbers |*p*1<=-<=*p*2|,<=|*p*2<=-<=*p*3|,<=...,<=|*p**n*<=-<=1<=-<=*p**n*| has exactly *k* distinct elements.

Input Specification:
The single line of the input contains two space-separated positive integers *n*, *k* (1<=≤<=*k*<=&lt;<=*n*<=≤<=105).

Output Specification:
Print *n* integers forming the permutation. If there are multiple answers, print any of them.

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

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

Note:
By |*x*| we denote the absolute value of number *x*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
       

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:


       The number of buildings in any input list is guaranteed to be in the range [0, 10000].
       The input list is already sorted in ascending order by the left x position Li.
       The output list must be sorted by the x position.
       There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a group of N friends who wish to enroll in a course together. The course has a maximum capacity of M students that can register for it. If there are K other students who have already enrolled in the course, determine if it will still be possible for all the N friends to do so or not.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- Each test case consists of a single line containing three integers N, M and K - the size of the friend group, the capacity of the course and the number of students already registered for the course.

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

For each test case, output Yes if it will be possible for all the N friends to register for the course. Otherwise output No.

You may print each character of Yes and No in uppercase or lowercase (for example, yes, yEs, YES will be considered identical).

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ M ≤ 100$
$0 ≤ K ≤ M$

----- Sample Input 1 ------ 
3
2 50 27
5 40 38
100 100 0

----- Sample Output 1 ------ 
Yes
No
Yes

----- explanation 1 ------ 
Test Case 1: The $2$ friends can enroll in the course as it has enough seats to accommodate them and the $27$ other students at the same time.

Test Case 2: The course does not have enough seats to accommodate the $5$ friends and the $38$ other students at the same time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another.

The game rules are like this. Firstly Alice chooses some color A, then Bob chooses some color B (A ≠ B). After each car they update the number of cars of their chosen color that have run past them. Let's define this numbers after i-th car cnt_{A}(i) and cnt_{B}(i).

  If cnt_{A}(i) > cnt_{B}(i) for every i then the winner is Alice.  If cnt_{B}(i) ≥ cnt_{A}(i) for every i then the winner is Bob.  Otherwise it's a draw. 

Bob knows all the colors of cars that they will encounter and order of their appearance. Alice have already chosen her color A and Bob now wants to choose such color B that he will win the game (draw is not a win). Help him find this color.

If there are multiple solutions, print any of them. If there is no such color then print -1.


-----Input-----

The first line contains two integer numbers n and A (1 ≤ n ≤ 10^5, 1 ≤ A ≤ 10^6) – number of cars and the color chosen by Alice.

The second line contains n integer numbers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^6) — colors of the cars that Alice and Bob will encounter in the order of their appearance.


-----Output-----

Output such color B (1 ≤ B ≤ 10^6) that if Bob chooses it then he will win the game. If there are multiple solutions, print any of them. If there is no such color then print -1.

It is guaranteed that if there exists any solution then there exists solution with (1 ≤ B ≤ 10^6).


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

Output
2

Input
5 2
2 2 4 5 3

Output
-1

Input
3 10
1 2 3

Output
4



-----Note-----

Let's consider availability of colors in the first example:   cnt_2(i) ≥ cnt_1(i) for every i, and color 2 can be the answer.  cnt_4(2) < cnt_1(2), so color 4 isn't the winning one for Bob.  All the other colors also have cnt_{j}(2) < cnt_1(2), thus they are not available. 

In the third example every color is acceptable except for 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a harder version of the problem. In this version, n ≤ 300 000.

Vasya is an experienced developer of programming competitions' problems. As all great minds at some time, Vasya faced a creative crisis. To improve the situation, Petya gifted him a string consisting of opening and closing brackets only. Petya believes, that the beauty of the bracket string is a number of its cyclical shifts, which form a correct bracket sequence.

To digress from his problems, Vasya decided to select two positions of the string (not necessarily distinct) and swap characters located at this positions with each other. Vasya will apply this operation exactly once. He is curious what is the maximum possible beauty he can achieve this way. Please help him.

We remind that bracket sequence s is called correct if: 

  * s is empty; 
  * s is equal to "(t)", where t is correct bracket sequence; 
  * s is equal to t_1 t_2, i.e. concatenation of t_1 and t_2, where t_1 and t_2 are correct bracket sequences. 



For example, "(()())", "()" are correct, while ")(" and "())" are not.

The cyclical shift of the string s of length n by k (0 ≤ k < n) is a string formed by a concatenation of the last k symbols of the string s with the first n - k symbols of string s. For example, the cyclical shift of string "(())()" by 2 equals "()(())".

Cyclical shifts i and j are considered different, if i ≠ j.

Input

The first line contains an integer n (1 ≤ n ≤ 300 000), the length of the string.

The second line contains a string, consisting of exactly n characters, where each of the characters is either "(" or ")".

Output

The first line should contain a single integer — the largest beauty of the string, which can be achieved by swapping some two characters.

The second line should contain integers l and r (1 ≤ l, r ≤ n) — the indices of two characters, which should be swapped in order to maximize the string's beauty.

In case there are several possible swaps, print any of them.

Examples

Input


10
()()())(()


Output


5
8 7


Input


12
)(()(()())()


Output


4
5 10


Input


6
)))(()


Output


0
1 1

Note

In the first example, we can swap 7-th and 8-th character, obtaining a string "()()()()()". The cyclical shifts by 0, 2, 4, 6, 8 of this string form a correct bracket sequence.

In the second example, after swapping 5-th and 10-th character, we obtain a string ")(())()()(()". The cyclical shifts by 11, 7, 5, 3 of this string form a correct bracket sequence.

In the third example, swap of any two brackets results in 0 cyclical shifts being correct bracket sequences. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:


Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:


Input: "cbbd"
Output: "bb"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Due to the frantical usage of the racket to kill flies, Marin has sustained a serious bodily injury known to the medical community as epicondylitis lateralis humeri. His grandma has advised smearing rakija over it, the doctor has prescribed a strong painkiller, but Marin has ignored every single advice and decided to look for the answer in integer sequences.

He has discovered a previously undiscovered sequence of integers and called it the xorbonacci sequence. The $n$-th element in the sequence is denoted with $x_ n$. The sequence is defined recursively in the following way:\begin{align*} x_1 & = a_1,\\ x_2 & = a_2,\\ & \ldots \\ x_ k & = a_ k,\\ x_ n & = x_{n-1} \oplus x_{n-2} \oplus \ldots \oplus x_{n-k}, \quad n > k\\ \end{align*}

Because of a reason only known to Marin, he determined that all his sorrows will go away if you answer his $Q$ queries defined with numbers $l$ and $r$. The answer to the query is represented with the value\begin{equation*} x_ l \oplus x_{l+1} \oplus \ldots \oplus x_{r-1} \oplus x_ r \end{equation*}

Help Marin and answer his queries.

Please note: The operation $\oplus $ is the operation of binary XOR.

-----Input-----
The first line of input contains the integer $K$ ($1 \leq K \leq 100000$) from the task. The following line contains $K$ integers that represent the first $K$ elements in the xorbonacci sequence. All numbers are smaller than $10^{18}$. The following line contains the integer $Q$ ($1 \leq Q \leq 10^6$) from the task. The $i$-th of the following $Q$ lines contains two integers $l_ i$ and $r_ i$ ($1 \leq l_ i \leq r_ i \leq 10^{18}$) that represent Marin’s $i$-th query.

-----Output-----
Each of the following $Q$ lines of output must contain the answers to Marin’s queries, the order being the same as the input.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
You are given a valid XML document, and you have to print the maximum level of nesting in it. Take the depth of the root as 0.

=====Input Format=====
The first line contains N, the number of lines in the XML document.
The next N lines follow containing the XML document.

=====Output Format=====
Output a single line, the integer value of the maximum level of nesting in the XML document.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a boolean 2D matrix grid of size n * m. You have to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is not equal to another (not rotated or reflected).
Example 1:
Input:
grid[][] = {{1, 1, 0, 0, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 1, 1}}
Output:
1
Explanation:
grid[][] = {{1, 1, 0, 0, 0}, 
            {1, 1, 0, 0, 0}, 
            {0, 0, 0, 1, 1}, 
            {0, 0, 0, 1, 1}}
Same colored islands are equal.
We have 2 equal islands, so we 
have only 1 distinct island.
Example 2:
Input:
grid[][] = {{1, 1, 0, 1, 1},
            {1, 0, 0, 0, 0},
            {0, 0, 0, 0, 1},
            {1, 1, 0, 1, 1}}
Output:
3
Explanation:
grid[][] = {{1, 1, 0, 1, 1}, 
            {1, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 1}, 
            {1, 1, 0, 1, 1}}
Same colored islands are equal.
We have 4 islands, but 2 of them
are equal, So we have 3 distinct islands.
Your Task:
You don't need to read or print anything. Your task is to complete the function countDistinctIslands() which takes the grid as an input parameter and returns the total number of distinct islands.
Expected Time Complexity: O(n * m)
Expected Space Complexity: O(n * m)
Constraints:
1 ≤ n, m ≤ 500
grid[i][j] == 0 or grid[i][j] == 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.

For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:

 - f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.
Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 3000
 - 1 \leq S \leq 3000
 - 1 \leq A_i \leq 3000

-----Input-----
Input is given from Standard Input in the following format:
N S
A_1 A_2 ... A_N

-----Output-----
Print the sum of f(L, R), modulo 998244353.

-----Sample Input-----
3 4
2 2 4

-----Sample Output-----
5

The value of f(L, R) for each pair is as follows, for a total of 5.
 - f(1,1) = 0
 - f(1,2) = 1 (for the sequence (1, 2))
 - f(1,3) = 2 (for (1, 2) and (3))
 - f(2,2) = 0
 - f(2,3) = 1 (for (3))
 - f(3,3) = 1 (for (3))

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are an employee of the Boxing And Processing Company and you are tasked with distributing boxes in one of the company’s enormous warehouses. At BAPC Ltd., boxes travel by conveyor belt. Two conveyor belts can be merged into one by letting one drop its content onto the other. On the other hand, a belt can be split into two by using a splitter, which sends a specific portion of its input to its first output and the rest to its second output. Normally your splitters are adjustable, being able to distribute its input over its output belts in any conceivable ratio, but in an attempt to cut costs your boss has ordered cheap knock-off splitters which can only distribute its input in a fixed ratio $a:b$. Instead of arguing with your boss about how you really need some $c:d$ splitters, you decide to make them yourself.

Of course, with your frugal boss, you have to watch your costs. You cannot build your splitter system in such a way that there are boxes that never leave the system. Nor can you use splitters that never receive any boxes. Finally, you cannot use too many $a: b$ splitters in total.

Given the ratios $a:b$ and $c:d$, construct a network of belts and at most $200$ knock-off $a:b$ splitters that has a single global input belt and two global output belts over which the global input is distributed in a ratio $c:d$.

Note that a splitter of ratio $x : y$ sends exactly $\frac x{x+y}$ of the incoming boxes to the first output and exactly $\frac y{x+y}$ of them to the second output.

-----Input-----
 - The first line contains two integers $1\leq a,b\leq 10^9$ with $a+b\leq 10^9$ denoting the ratio $a:b$ of your knock-off splitter.
 - The second line contains two integers $1\leq c,d\leq 10^9$ with $c+d\leq 10^9$ denoting the ratio $c:d$ of your desired splitter.

-----Output-----
 - The first line contains an integer $1\leq n\leq 200$, the number of $a:b$ splitters used.
 - Then follow $n$ lines, the $i$-th of which contains two integers $-2\leq l_ i,r_ i<n$.

Here $l_ i$ is the index of the splitter connected to the left output of the $i$-th splitter, where it deposits $a/(a+b)$ of its input. Similarly $r_ i$ is the index of the splitter receiving $b/(a+b)$ of the input of the $i$-th splitter. The splitters are indexed starting from $0$. The global input is connected to splitter $0$. The special values $-1$ and $-2$ for $l_ i$ and $r_ i$ correspond to the first and second global output, which need to receive $c/(c+d)$ and $d/(c+d)$ of the global input respectively.

Note that you cannot place a splitter in such a way that no box ever reaches it, nor in such a way that a box that passes through it will never reach the output.

If there are multiple possible solutions, you may output any one of them.

-----Examples-----
Sample Input 1:
2 3
3 2
Sample Output 1:
1
-2 -1

Sample Input 2:
1 2
3 4
Sample Output 2:
3
-1 1
2 1
0 -2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We need to write some code to return the original price of a product, the return type must be of type decimal and the number must be rounded to two decimal places.

We will be given the sale price (discounted price), and the sale percentage, our job is to figure out the original price.


### For example:

Given an item at $75 sale price after applying a 25% discount, the function should return the original price of that item before applying the sale percentage, which is ($100.00) of course, rounded to two decimal places.


DiscoverOriginalPrice(75, 25) => 100.00M where 75 is the sale price (discounted price), 25 is the sale percentage and 100 is the original price

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your job at E-Corp is both boring and difficult. It isn't made any easier by the fact that everyone constantly wants to have a meeting with you, and that the meeting rooms are always taken!

In this kata, you will be given an array. Each value represents a meeting room. Your job? Find the **first** empty one and return its index (N.B. There may be more than one empty room in some test cases). 

'X' --> busy
'O' --> empty

If all rooms are busy, return 'None available!'.


More in this series:

The Office I - Outed
The Office II - Boredeom Score
The Office III - Broken Photocopier
The Office V - Find a Chair

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

Two or more arrays can be concatenated together using the concatenate function with a
tuple of the arrays to be joined:

import numpy

array_1 = numpy.array([1,2,3])
array_2 = numpy.array([4,5,6])
array_3 = numpy.array([7,8,9])

print numpy.concatenate((array_1, array_2, array_3))    

#Output
[1 2 3 4 5 6 7 8 9]

If an array has more than one dimension, it is possible to specify the axis along which multiple arrays are concatenated. By default, it is along the first dimension.

import numpy

array_1 = numpy.array([[1,2,3],[0,0,0]])
array_2 = numpy.array([[0,0,0],[7,8,9]])

print numpy.concatenate((array_1, array_2), axis = 1)   

#Output
[[1 2 3 0 0 0]
 [0 0 0 7 8 9]]    

Task  

You are given two integer arrays of size $N$X$\mbox{P}$ and $\mbox{M}$X$\mbox{P}$ ($N$ & $\mbox{M}$ are rows, and $\mbox{P}$ is the column).  Your task is to concatenate the arrays along axis $\mbox{o}$.

Input Format

The first line contains space separated integers $N$, $\mbox{M}$ and $\mbox{P}$. 

The next $N$ lines contains the space separated elements of the $\mbox{P}$ columns. 

After that, the next $\mbox{M}$ lines contains the space separated elements of the $\mbox{P}$ columns.

Output Format

Print the concatenated array of size $(N+M)$X$\mbox{P}$.

Sample Input
4 3 2
1 2
1 2 
1 2
1 2
3 4
3 4
3 4 

Sample Output
[[1 2]
 [1 2]
 [1 2]
 [1 2]
 [3 4]
 [3 4]
 [3 4]]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
KK has a crush on a girl in his class. In this valentines day he planned to propose her. 

KK's crush will accept his proposal if KK solves the following problem:-

Given an array A of n numbers and k queries. In each query we have a number x .Now KK has to tell to whether number x exists in array or not.

Can you help KK?

*Input :- *

First line contains number of test cases t.First line of each test case contains number of elements n in array A. Second line contains n elements of array of A.Third line contains k(number of queries).
Following k lines contain a number x.

*Output :- *

For each query in a test case print "Yes" or "No" ( Quotes for clarity ).

Constraints:-

1 ≤ t ≤ 12  (t= Number of test cases in each input file).

1 ≤ n ≤ 10^5  (n=number of elements in array).

-10^5 ≤ A[i] ≤ 10^5  (A[i]=ith element of array).

1 ≤ k ≤ 10^4   (k=number of queries).

-10^5 ≤ x ≤ 10^5  (x=Number asked to search for in each query).

SAMPLE INPUT
2
5
12 13 -4 3 2
6
15
11
13
2
3
12
6
12 3 -67 67 34 2
4
4
5
67
7

SAMPLE OUTPUT
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No

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