vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a set of size $m$ with integer elements between $0$ and $2^{n}-1$ inclusive. Let's build an undirected graph on these integers in the following way: connect two integers $x$ and $y$ with an edge if and only if $x \& y = 0$. Here $\&$ is the bitwise AND operation. Count the number of connected components in that graph.


-----Input-----

In the first line of input there are two integers $n$ and $m$ ($0 \le n \le 22$, $1 \le m \le 2^{n}$).

In the second line there are $m$ integers $a_1, a_2, \ldots, a_m$ ($0 \le a_{i} < 2^{n}$) — the elements of the set. All $a_{i}$ are distinct.


-----Output-----

Print the number of connected components.


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

Output
2

Input
5 5
5 19 10 20 12

Output
2



-----Note-----

Graph from first sample:

$0$

Graph from second sample:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This challenge is based on [the kata](https://www.codewars.com/kata/n-smallest-elements-in-original-order) by GiacomoSorbi. Before doing this one it is advisable to complete the non-performance version first.

___

# Task

You will be given an array of random integers and a number `n`. You have to extract `n` smallest integers out of it **preserving the original order**.

# Examples

```python
performant_smallest([1, 2, 3, 4, 5], 3)     ==   [1, 2, 3]
performant_smallest([5, 4, 3, 2, 1], 3)     ==   [3, 2, 1]
performant_smallest([1, 2, 3, 4, 1], 3)     ==   [1, 2, 1]
performant_smallest([2, 1, 3, 2, 3], 3)     ==   [2, 1, 2]
```

# Notes

* There will be duplicates in the array, and they have to be returned in the order of their each separate appearence.
* This kata is an example of the "know your data" principle. Remember this while searching for the correct approach.

# Performance tests

```python
Tests: 15
Array size: 800,000
Values range: [1; 50]
Number of elements to return: 25-50% of the array
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three positive integers N, x, and y.

Count the number of arrays P of length N such that:
P_{1} = P_{N} = 1
There are exactly x indices i such that P_{i}=1
There are exactly y indices i such that P_{i}=2
There are exactly N-x-y indices i such that P_{i}=3
P_{i} \neq P_{i+1} for each 1 ≤ i < N

Since the answer can be large, output it modulo 998244353.

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

- The first and only line of input will contain three space-separated integers N, x and y.

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

Output a single integer: the number of arrays obtained, modulo 998244353.

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

$3 ≤ N ≤ 2 \cdot 10^{6}$
$2 ≤ x ≤ N-1$
$1 ≤ y ≤ N-2$
$x + y ≤ N$

----- Sample Input 1 ------ 
5 3 1

----- Sample Output 1 ------ 
2
----- explanation 1 ------ 

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

----- Sample Output 2 ------ 
44
----- explanation 2 ------ 
Test case $1$: Only two valid arrays are possible: 
- $[1,2,1,3,1]$
- $[1,3,1,2,1]$

Test case $2$: A couple of valid arrays are $[1, 2, 3, 1, 2 ,3, 1, 2, 3, 1]$ and $[1, 3, 2, 1, 3, 1, 2, 3, 2, 1]$. It can be verified that there are $44$ in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nandu and Rani (husband and wife) live in a city consisting of N houses (1, 2, 3, ... , N) and N-1 roads, each road being of length 1 Km and connecting some 2 houses. Moreover, every house is connected to at least one other house. Nandu and Rani live in house 1. 

Nandu is really hungry and wants to eat Vada Pav. Rani, being a caring wife, doesn't want Nandu to spoil his own health. So, she has placed one Vada Pav in each and every house of the city. Nandu has to walk all over the city if he wants to eat those Vada Pavs. Nandu really likes Vada Pavs and decides to eat all of them. However, he doesn't like walking. So he decides he will stay back in the house in which he eats the last Vada Pav.

What is the minimum distance (in Km) Nandu has to travel to eat all the Vada Pavs ?
Input
The first line consists of N. Then, N-1 lines follow, each consisting of 2 space separated integers i and j, denoting that there is a road connecting houses i and j. 
Output
Print a single integer, the minimum distance (in Km) Nandu has to travel to eat all the Vada Pavs.
Constraints
1 ≤ N ≤ 10^3
1 ≤ i, j ≤ N

Author : Shreyans
Tester : Ravi 

SAMPLE INPUT
5
1 2
2 3
1 4
4 5

SAMPLE OUTPUT
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vadim is really keen on travelling. Recently he heard about kayaking activity near his town and became very excited about it, so he joined a party of kayakers.

Now the party is ready to start its journey, but firstly they have to choose kayaks. There are 2·n people in the group (including Vadim), and they have exactly n - 1 tandem kayaks (each of which, obviously, can carry two people) and 2 single kayaks. i-th person's weight is w_{i}, and weight is an important matter in kayaking — if the difference between the weights of two people that sit in the same tandem kayak is too large, then it can crash. And, of course, people want to distribute their seats in kayaks in order to minimize the chances that kayaks will crash.

Formally, the instability of a single kayak is always 0, and the instability of a tandem kayak is the absolute difference between weights of the people that are in this kayak. Instability of the whole journey is the total instability of all kayaks.

Help the party to determine minimum possible total instability! 


-----Input-----

The first line contains one number n (2 ≤ n ≤ 50).

The second line contains 2·n integer numbers w_1, w_2, ..., w_2n, where w_{i} is weight of person i (1 ≤ w_{i} ≤ 1000).


-----Output-----

Print minimum possible total instability.


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

Output
1

Input
4
1 3 4 6 3 4 100 200

Output
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Road Runner bought a piece of land in the middle of a desert for a nominal amount. It turns out that the piece of land is now worth millions of dollars as it has an oil reserve under it. Mr. Road Runner contacts the ACME corp to set up the oil wells on his land. Setting up oil wells is a costly affair and the charges of setting up oil wells are as follows. 

The rectangular plot bought by Mr. Road Runner is divided into r * c blocks. Only some blocks are suitable for setting up the oil well and these blocks have been marked. ACME charges nothing for building the first oil well. For every subsequent oil well built, the cost would be the maximum ACME distance between the new oil well and the existing oil wells. 

If (x,y) is the position of the block where a new oil well is setup and (x1, y1) is the position of the block of an existing oil well, the ACME distance is given by 

max(|x-x1|, |y-y1|)

the maximum ACME distance is the maximum among all the ACME distance between existing oil wells and new wells. 

If the distance of any two adjacent blocks (horizontal or vertical) is considered 1 unit, what is the minimum cost (E) in units it takes to set up oil wells across all the marked blocks?

Input Format

The first line of the input contains two space separated integers r *c*. 

r lines follow each containing c space separated integers. 

1 indicates that the block is suitable for setting up an oil well, whereas 0 isn't. 

r c  
M11 M12 ... M1c  
M21 M22 ... M2c  
...  
Mr1 Mr2 ... Mrc  

Constraints
1 <= r, c <= 50

Output Format

Print the minimum value E as the answer. 

Sample Input
3 4
1 0 0 0
1 0 0 0
0 0 1 0

Sample Output
3  

Explanation

(1, 1) (2, 1) (3, 3) are the places where are to be setup. 

There are 3! = 6 ways to do it. 

(1, 1) (2, 1) (3, 3) ==> cost = 0 + 1 + 2 = 3 

(1, 1) (3, 3) (2, 1) ==> cost = 0 + 2 + 2 = 4 

(2, 1) (1, 1) (3, 3) ==> cost = 0 + 1 + 2 = 3 

(2, 1) (3, 3) (1, 1) ==> cost = 0 + 2 + 2 = 4 

(3, 3) (1, 1) (2, 1) ==> cost = 0 + 2 + 2 = 4 

(3, 3) (2, 1) (1, 1) ==> cost = 0 + 2 + 2 = 4  

So E = 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Devu, the Dumb Guy

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Devu is a dumb guy, his learning curve is very slow. You are supposed to teach him *n* subjects, the *i**th* subject has *c**i* chapters. When you teach him, you are supposed to teach all the chapters of a subject continuously.

Let us say that his initial per chapter learning power of a subject is *x* hours. In other words he can learn a chapter of a particular subject in *x* hours.

Well Devu is not complete dumb, there is a good thing about him too. If you teach him a subject, then time required to teach any chapter of the next subject will require exactly 1 hour less than previously required (see the examples to understand it more clearly). Note that his per chapter learning power can not be less than 1 hour.

You can teach him the *n* subjects in any possible order. Find out minimum amount of time (in hours) Devu will take to understand all the subjects and you will be free to do some enjoying task rather than teaching a dumb guy.

Please be careful that answer might not fit in 32 bit data type.

Input Specification:
The first line will contain two space separated integers *n*, *x* (1<=≤<=*n*,<=*x*<=≤<=105). The next line will contain *n* space separated integers: *c*1,<=*c*2,<=...,<=*c**n* (1<=≤<=*c**i*<=≤<=105).

Output Specification:
Output a single integer representing the answer to the problem.

Demo Input:
['2 3\n4 1\n', '4 2\n5 1 2 1\n', '3 3\n1 1 1\n']

Demo Output:
['11\n', '10\n', '6\n']

Note:
Look at the first example. Consider the order of subjects: 1, 2. When you teach Devu the first subject, it will take him 3 hours per chapter, so it will take 12 hours to teach first subject. After teaching first subject, his per chapter learning time will be 2 hours. Now teaching him second subject will take 2 × 1 = 2 hours. Hence you will need to spend 12 + 2 = 14 hours.

Consider the order of subjects: 2, 1. When you teach Devu the second subject, then it will take him 3 hours per chapter, so it will take 3 × 1 = 3 hours to teach the second subject. After teaching the second subject, his per chapter learning time will be 2 hours. Now teaching him the first subject will take 2 × 4 = 8 hours. Hence you will need to spend 11 hours.

So overall, minimum of both the cases is 11 hours.

Look at the third example. The order in this example doesn't matter. When you teach Devu the first subject, it will take him 3 hours per chapter. When you teach Devu the second subject, it will take him 2 hours per chapter. When you teach Devu the third subject, it will take him 1 hours per chapter. In total it takes 6 hours.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vika has *n* jars with paints of distinct colors. All the jars are numbered from 1 to *n* and the *i*-th jar contains *a**i* liters of paint of color *i*.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1<=×<=1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color *x*, then the next square will be painted in color *x*<=+<=1. In case of *x*<==<=*n*, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109), where *a**i* is equal to the number of liters of paint in the *i*-th jar, i.e. the number of liters of color *i* that Vika has.

Output Specification:
The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.

Demo Input:
['5\n2 4 2 3 3\n', '3\n5 5 5\n', '6\n10 10 10 1 10 10\n']

Demo Output:
['12\n', '15\n', '11\n']

Note:
In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Print the circumference of a circle of radius R.

-----Constraints-----
 - 1 \leq R \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
R

-----Output-----
Print the circumference of the circle.
Your output is considered correct if and only if its absolute or relative error from our answer is at most 10^{-2}.

-----Sample Input-----
1

-----Sample Output-----
6.28318530717958623200

Since we accept an absolute or relative error of at most 10^{-2}, 6.28 is also an acceptable output, but 6 is not.

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

You were asked by a company to create a program. The company has $ N $ jobs, and each job is numbered from $ 1 $ to $ N $. There are $ M_i $ prerequisite jobs $ X_ {i, j} $ in job $ i $, and work $ X_ {i, j} $ is performed before job $ X_ {i, j} $. And work $ i $ suffers a great loss.

So ask you to find the number of jobs you lost when you did all the jobs in the order that minimized the number of jobs you lost.

Constraints

The input satisfies the following conditions.

* $ 1 \ le N \ le 10 ^ 5 $
* $ 0 \ le M_i \ le N $
* Sum of $ M_i $ does not exceed $ 10 ^ 5 $
* $ 1 \ le X_ {i, j} \ le min (i + 1, N) $

Input

All inputs are given as integers in the following format:


$ N $
$ M_1 $ $ X_ {1,1} $ $ X_ {1,2} $ ... $ X_ {1, M_1} $
$ M_2 $ $ X_ {2,1} $ $ X_ {2,2} $ ... $ X_ {2, M_2} ​​$
::
$ M_N $ $ X_ {N, 1} $ $ X_ {N, 2} $ ... $ X_ {N, M_N} $


The number of jobs $ N $ is given to the $ 1 $ line.
The following $ N $ line gives information on the prerequisite work. Information on work $ i $ is given on the $ i + 1 $ line, separated by blanks. $ M_i $ represents the number of jobs that are the premise of work $ i $, and $ X_ {i, j} $ is the number of jobs that are the premise of job $ i $.

Output

When all the jobs are done in the order that minimizes the number of jobs incurred, the number of jobs incurred at that time is output in one line.

Examples

Input

2
1 1
0


Output

1


Input

3
3 2 1 2
0
1 2


Output

1


Input

5
1 2
1 3
2 1 2
3 1 3 5
0


Output

1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$ of length $n$ consisting of lowercase Latin letters. You may apply some operations to this string: in one operation you can delete some contiguous substring of this string, if all letters in the substring you delete are equal. For example, after deleting substring bbbb from string abbbbaccdd we get the string aaccdd.

Calculate the minimum number of operations to delete the whole string $s$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 500$) — the length of string $s$.

The second line contains the string $s$ ($|s| = n$) consisting of lowercase Latin letters.


-----Output-----

Output a single integer — the minimal number of operation to delete string $s$.


-----Examples-----
Input
5
abaca

Output
3
Input
8
abcddcba

Output
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Curse your rival! Every year at the annual Rock Paper Scissors tournament, you have made it to the final match. (Your Rock technique is unmatched, and your Paper cuts to the bone! Your Scissors need a little work, though.) But every year, he defeats you, even though his moves appear entirely random! And he claims to the press that he simply cannot be beaten. What is his secret?

Fortunately, you think you have figured it out. This year, just before the tournament, you caught him visiting various shamans around town. Aha! He is using the supernatural against you! You figured two can play at this game. So you went and visited a set of fortune-tellers, who have each used a Tarot deck to predict a sequence that your rival will end up using, sometime during the match.

However, your initial excitement has passed, and now you are feeling a little silly. This cannot possibly work, right? In the end it feels like you have paid good money for a fraudulent, random set of predictions. Oh well; you might as well keep an eye out for some of them during the match. But which predictions will you use?

In the final match, you and your rival will play $n$ rounds of Rock Paper Scissors. In each round, your rival and you will both choose one of the three options (Rock, Paper, or Scissors). Based on your selections, a winner of the round will be determined (exactly how is irrelevant to this problem).

Given the length of the final match and the various predictions, sort them in order of how likely they are to appear sometime during the match as a contiguous sequence of options chosen by your rival, assuming he is choosing his symbol in each round independently and uniformly at random.

-----Input-----
The first line of input contains two integers $n$ ($1\leq n \leq 10^6$), the number of rounds in the final match, and $s$ ($1 \leq s \leq 10$), the number of sequences. The remaining $s$ lines each describe a prediction, consisting of a string of characters ‘R’, ‘P’, and ‘S’. All predictions have the same length, which is between $1$ and $n$ characters long, inclusive, and no longer than $10^5$.

-----Output-----
Display all of the predictions, sorted by decreasing likelihood of appearance sometime during the final match. In the case of tied predictions, display them in the same order as in the input.

-----Examples-----
Sample Input:
3 4
PP
RR
PS
SS
Sample Output:
PS
PP
RR
SS

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem. You have to use flush operation right after printing each line. For example, in C++ you should use function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

In this problem, you need to find maximal and minimal elements of an array. What could be simpler?

You can imagine that the jury has an array, and initially you know the only number n — array's length.

Array's elements are numbered from 1 to n. You are allowed to compare two elements of the array by using their indices i and j. There are three possible responses to this query: '<' (if ai is less than aj), '=' (if ai is equal to aj) and finally '>' (if ai is greater than aj).

It's known that it's always possible to find both maximal and minimal elements of the array by using no more than <image> comparisons, where ⌈ x⌉ is the result of rounding x up.

Write the program that will find positions of the minimum and the maximum in the jury's array of length n, by using no more than f(n) comparisons.

Interaction

Each test for this problem will contain one or more arrays. You have to find positions of minimal and maximal elements for each of these arrays. The first line of the input contains integer T (1 ≤ T ≤ 1000) — number of arrays in the test.

Thus, at the beginning, you program should read number T, and then it should solve the problem for T jury's arrays one by one.

Then input for each array goes. Firstly, your program has to read the number n (1 ≤ n ≤ 50) — the length of the array. It will be provided in the next line of the input.

Further, your program can perform comparisons or report that the answer is found.

  * To perform a comparison, you have to output string of the following pattern «? i j» (i and j must be integer numbers from 1 to n) — the indices of the elements to compare in the current query. 
  * To report the indices of minimal and maximal elements of the hidden array, your program have to output a line in the form «! i j» (i and j must be integer numbers from 1 to n), where i is an index of the minimal element of array, and j is an index of the maximal element of the array. If there are several possible answers to the problem, you can output any of them. 



There are several possible responses for a comparison:

  * '<' — if ai is less than aj, 
  * '=' — if ai is equal to aj, 
  * '>' — if ai is greater than aj. 



For an array of length n your program can make at most <image> comparisons. Note that the operation of reporting an answer («! i j» ) is not included into the value of f(n).

After the answer is reported, your program has to solve the problem for the next array or it should terminate if all T arrays are processed.

Example

Input

2
2
 
&gt;
 
3
 
=
 
=
 

Output

 
 
? 1 2
 
! 2 1
 
? 3 1
 
? 2 1
 
! 2 3

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

You have to partition the elements of the array into some [subsequences] such that:
Each element A_{i} (1 ≤ i ≤ N) belongs to exactly one subsequence.
The [mean] of the mean of subsequences is maximised.

Formally, let S_{1}, S_{2}, \dots, S_{K} denote K subsequences of array A such that each element A_{i} (1 ≤ i ≤ N) belongs to exactly one subsequence S_{j} (1 ≤ j ≤ K).  
Let X_{j} (1 ≤ j ≤ K) denote the mean of the elements of subsequence S_{j}. You need to maximise the value \frac{\sum_{j=1}^K X_{j}}{K}.

Print the maximum value. The answer is considered correct if the relative error is less than 10^{-6}.

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

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case consists of a single integer N - denoting the length of array A.
- Second line of each test case consists of N space-separated integers A_{1}, A_{2}, \ldots, A_{N} - denoting the array A.

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

For each test case, output in a single line, the maximum possible mean of mean of subsequences. The answer is considered correct if the relative error is less than 10^{-6}.

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

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

----- Sample Input 1 ------ 
3
2
10 20
3
1 2 3
5
50 50 50 50 50

----- Sample Output 1 ------ 
15
2.25
50

----- explanation 1 ------ 
Test Case $1$: We can partition the array in $2$ ways - $(\{10\}, \{20\})$ or $(\{10,20\})$. In both cases, mean of mean of subsequences comes out to be $15$.

Test Case $2$: The optimal partition is $(\{1, 2\}, \{3\})$.
- Mean of first subsequence $ = \frac{1+2}{2} = 1.5$.
- Mean of second subsequence $ = \frac{3}{1} = 3$.

Thus, mean of mean of subsequences is $\frac{1.5+3}{2} = \frac{4.5}{2} = 2.25$.

Test Case $3$: Any partition will yield the mean of mean of subsequences as $50$.

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