vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You have a bag of size $n$. Also you have $m$ boxes. The size of $i$-th box is $a_i$, where each $a_i$ is an integer non-negative power of two.

You can divide boxes into two parts of equal size. Your goal is to fill the bag completely.

For example, if $n = 10$ and $a = [1, 1, 32]$ then you have to divide the box of size $32$ into two parts of size $16$, and then divide the box of size $16$. So you can fill the bag with boxes of size $1$, $1$ and $8$.

Calculate the minimum number of divisions required to fill the bag of size $n$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^{18}, 1 \le m \le 10^5$) — the size of bag and the number of boxes, respectively.

The second line of each test case contains $m$ integers $a_1, a_2, \dots , a_m$ ($1 \le a_i \le 10^9$) — the sizes of boxes. It is guaranteed that each $a_i$ is a power of two.

It is also guaranteed that sum of all $m$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print one integer — the minimum number of divisions required to fill the bag of size $n$ (or $-1$, if it is impossible).


-----Example-----
Input
3
10 3
1 32 1
23 4
16 1 4 1
20 5
2 1 16 1 8

Output
2
-1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string is a palindrome if it reads the same from the left to the right and from the right to the left. For example, the strings "kek", "abacaba", "r" and "papicipap" are palindromes, while the strings "abb" and "iq" are not.

A substring $s[l \ldots r]$ ($1 \leq l \leq r \leq |s|$) of a string $s = s_{1}s_{2} \ldots s_{|s|}$ is the string $s_{l}s_{l + 1} \ldots s_{r}$.

Anna does not like palindromes, so she makes her friends call her Ann. She also changes all the words she reads in a similar way. Namely, each word $s$ is changed into its longest substring that is not a palindrome. If all the substrings of $s$ are palindromes, she skips the word at all.

Some time ago Ann read the word $s$. What is the word she changed it into?


-----Input-----

The first line contains a non-empty string $s$ with length at most $50$ characters, containing lowercase English letters only.


-----Output-----

If there is such a substring in $s$ that is not a palindrome, print the maximum length of such a substring. Otherwise print $0$.

Note that there can be multiple longest substrings that are not palindromes, but their length is unique.


-----Examples-----
Input
mew

Output
3

Input
wuffuw

Output
5

Input
qqqqqqqq

Output
0



-----Note-----

"mew" is not a palindrome, so the longest substring of it that is not a palindrome, is the string "mew" itself. Thus, the answer for the first example is $3$.

The string "uffuw" is one of the longest non-palindrome substrings (of length $5$) of the string "wuffuw", so the answer for the second example is $5$.

All substrings of the string "qqqqqqqq" consist of equal characters so they are palindromes. This way, there are no non-palindrome substrings. Thus, the answer for the third example is $0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

For positive integers $a$ and $b$, we say that a fraction $\frac{a}{b}$ is *good* if it is equal to $\frac{m}{m+1}$ for some positive integer $m$.

You are given an integer $N$. Find the number of pairs of integers $i, j$ such that $1 ≤ i, j ≤ N$ and the fraction $\frac{i}{i+1} \cdot \frac{j+1}{j}$ is good.

------  Input ------
The first and only line of the input contains a single integer $N$.

------  Output ------
Print a single line containing one integer ― the number of pairs of integers $i, j$ ($1 ≤ i, j ≤ N$) such that $\frac{i}{i + 1} \cdot \frac{j+1}{j}$ is good.

------  Constraints ------
$1 ≤ N ≤ 1,000,000$

------  Subtasks ------
Subtask #1 (5 points): $1 ≤ N ≤ 2,000$

Subtask #2 (10 points): $1 ≤ N ≤ 100,000$

Subtask #3 (85 points): original constraints

----- Sample Input 1 ------ 
5
----- Sample Output 1 ------ 
8
----- explanation 1 ------ 
The following eight pairs $(i, j)$ give good fractions: $(1,2)$, $(1,3)$, $(2,3)$, $(2,4)$, $(2,5)$, $(3,4)$, $(3,5)$ and $(4,5)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I assume most of you are familiar with the ancient legend of the rice (but I see wikipedia suggests [wheat](https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem), for some reason) problem, but a quick recap for you: a young man asks as a compensation only `1` grain of rice for the first square, `2` grains for the second, `4` for the third, `8` for the fourth and so on, always doubling the previous.

Your task is pretty straightforward (but not necessarily easy): given an amount of grains, you need to return up to which square of the chessboard one should count in order to get at least as many.

As usual, a few examples might be way better than thousands of words from me:

```python
squares_needed(0) == 0
squares_needed(1) == 1
squares_needed(2) == 2
squares_needed(3) == 2
squares_needed(4) == 3
```

Input is always going to be valid/reasonable: ie: a non negative number; extra cookie for *not* using a loop to compute square-by-square (at least not directly) and instead trying a smarter approach [hint: some peculiar operator]; a trick converting the number might also work: impress me!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider all binary strings of length $m$ ($1 \le m \le 60$). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly $2^m$ such strings in total.

The string $s$ is lexicographically smaller than the string $t$ (both have the same length $m$) if in the first position $i$ from the left in which they differ, we have $s[i] < t[i]$. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set $n$ ($1 \le n \le \min(2^m-1, 100)$) distinct binary strings $a_1, a_2, \ldots, a_n$, each of length $m$. Thus, the set will have $k=2^m-n$ strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from $0$ to $k-1$. Print the string whose index is $\lfloor \frac{k-1}{2} \rfloor$ (such an element is called median), where $\lfloor x \rfloor$ is the rounding of the number down to the nearest integer.

For example, if $n=3$, $m=3$ and $a=[$010, 111, 001$]$, then after removing the strings $a_i$ and sorting, the result will take the form: $[$000, 011, 100, 101, 110$]$. Thus, the desired median is 100.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains integers $n$ ($1 \le n \le \min(2^m-1, 100)$) and $m$ ($1 \le m \le 60$), where $n$ is the number of strings to remove, and $m$ is the length of binary strings. The next $n$ lines contain $a_1, a_2, \ldots, a_n$ — distinct binary strings of length $m$.

The total length of all given binary strings in all test cases in one test does not exceed $10^5$.


-----Output-----

Print $t$ answers to the test cases. For each test case, print a string of length $m$ — the median of the sorted sequence of remaining strings in the corresponding test case.


-----Example-----
Input
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

Output
100
010
0
1
11



-----Note-----

The first test case is explained in the statement.

In the second test case, the result after removing strings and sorting is $[$001, 010, 101, 110$]$. Therefore, the desired median is 010.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a program which prints multiplication tables in the following format:


1x1=1
1x2=2
.
.
9x8=72
9x9=81




Input

No input.

Output


1x1=1
1x2=2
.
.
9x8=72
9x9=81


Example

Input




Output

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Queries for Number of Palindromes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got a string *s*<==<=*s*1*s*2... *s*|*s*| of length |*s*|, consisting of lowercase English letters. There also are *q* queries, each query is described by two integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=|*s*|). The answer to the query is the number of substrings of string *s*[*l**i*... *r**i*], which are palindromes.

String *s*[*l*... *r*]<==<=*s**l**s**l*<=+<=1... *s**r* (1<=≤<=*l*<=≤<=*r*<=≤<=|*s*|) is a substring of string *s*<==<=*s*1*s*2... *s*|*s*|.

String *t* is called a palindrome, if it reads the same from left to right and from right to left. Formally, if *t*<==<=*t*1*t*2... *t*|*t*|<==<=*t*|*t*|*t*|*t*|<=-<=1... *t*1.

Input Specification:
The first line contains string *s* (1<=≤<=|*s*|<=≤<=5000). The second line contains a single integer *q* (1<=≤<=*q*<=≤<=106) — the number of queries. Next *q* lines contain the queries. The *i*-th of these lines contains two space-separated integers *l**i*,<=*r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=|*s*|) — the description of the *i*-th query.

It is guaranteed that the given string consists only of lowercase English letters.

Output Specification:
Print *q* integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Demo Input:
['caaaba\n5\n1 1\n1 4\n2 3\n4 6\n4 5\n']

Demo Output:
['1\n7\n3\n4\n2\n']

Note:
Consider the fourth query in the first test case. String *s*[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rectangular parallelepiped with sides of positive integer lengths $A$, $B$ and $C$. 

Find the number of different groups of three integers ($a$, $b$, $c$) such that $1\leq a\leq b\leq c$ and parallelepiped $A\times B\times C$ can be paved with parallelepipeds $a\times b\times c$. Note, that all small parallelepipeds have to be rotated in the same direction.

For example, parallelepiped $1\times 5\times 6$ can be divided into parallelepipeds $1\times 3\times 5$, but can not be divided into parallelepipeds $1\times 2\times 3$.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

Each of the next $t$ lines contains three integers $A$, $B$ and $C$ ($1 \leq A, B, C \leq 10^5$) — the sizes of the parallelepiped.


-----Output-----

For each test case, print the number of different groups of three points that satisfy all given conditions.


-----Example-----
Input
4
1 1 1
1 6 1
2 2 2
100 100 100

Output
1
4
4
165



-----Note-----

In the first test case, rectangular parallelepiped $(1, 1, 1)$ can be only divided into rectangular parallelepiped with sizes $(1, 1, 1)$.

In the second test case, rectangular parallelepiped $(1, 6, 1)$ can be divided into rectangular parallelepipeds with sizes $(1, 1, 1)$, $(1, 1, 2)$, $(1, 1, 3)$ and $(1, 1, 6)$.

In the third test case, rectangular parallelepiped $(2, 2, 2)$ can be divided into rectangular parallelepipeds with sizes $(1, 1, 1)$, $(1, 1, 2)$, $(1, 2, 2)$ and $(2, 2, 2)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
SmallR is an archer. SmallR is taking a match of archer with Zanoes. They try to shoot in the target in turns, and SmallR shoots first. The probability of shooting the target each time is $\frac{a}{b}$ for SmallR while $\frac{c}{d}$ for Zanoes. The one who shoots in the target first should be the winner.

Output the probability that SmallR will win the match.


-----Input-----

A single line contains four integers $a, b, c, d(1 \leq a, b, c, d \leq 1000,0 < \frac{a}{b} < 1,0 < \frac{c}{d} < 1)$.


-----Output-----

Print a single real number, the probability that SmallR will win the match.

The answer will be considered correct if the absolute or relative error doesn't exceed 10^{ - 6}.


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

Output
0.666666666667

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food. 

Iahub asks Iahubina: can you build a rooted tree, such that

  each internal node (a node with at least one son) has at least two sons;  node i has c_{i} nodes in its subtree? 

Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain n nodes.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 24). Next line contains n positive integers: the i-th number represents c_{i} (1 ≤ c_{i} ≤ n).


-----Output-----

Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes). 


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

Output
YES
Input
5
1 1 5 2 1

Output
NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Anya loves to watch horror movies. In the best traditions of horror, she will be visited by *m* ghosts tonight. Anya has lots of candles prepared for the visits, each candle can produce light for exactly *t* seconds. It takes the girl one second to light one candle. More formally, Anya can spend one second to light one candle, then this candle burns for exactly *t* seconds and then goes out and can no longer be used.

For each of the *m* ghosts Anya knows the time at which it comes: the *i*-th visit will happen *w**i* seconds after midnight, all *w**i*'s are distinct. Each visit lasts exactly one second.

What is the minimum number of candles Anya should use so that during each visit, at least *r* candles are burning? Anya can start to light a candle at any time that is integer number of seconds from midnight, possibly, at the time before midnight. That means, she can start to light a candle integer number of seconds before midnight or integer number of seconds after a midnight, or in other words in any integer moment of time.

Input Specification:
The first line contains three integers *m*, *t*, *r* (1<=≤<=*m*,<=*t*,<=*r*<=≤<=300), representing the number of ghosts to visit Anya, the duration of a candle's burning and the minimum number of candles that should burn during each visit. 

The next line contains *m* space-separated numbers *w**i* (1<=≤<=*i*<=≤<=*m*, 1<=≤<=*w**i*<=≤<=300), the *i*-th of them repesents at what second after the midnight the *i*-th ghost will come. All *w**i*'s are distinct, they follow in the strictly increasing order.

Output Specification:
If it is possible to make at least *r* candles burn during each visit, then print the minimum number of candles that Anya needs to light for that.

If that is impossible, print <=-<=1.

Demo Input:
['1 8 3\n10\n', '2 10 1\n5 8\n', '1 1 3\n10\n']

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

Note:
Anya can start lighting a candle in the same second with ghost visit. But this candle isn't counted as burning at this visit.

It takes exactly one second to light up a candle and only after that second this candle is considered burning; it means that if Anya starts lighting candle at moment x, candle is buring from second x + 1 to second x + t inclusively.

In the first sample test three candles are enough. For example, Anya can start lighting them at the 3-rd, 5-th and 7-th seconds after the midnight.

In the second sample test one candle is enough. For example, Anya can start lighting it one second before the midnight.

In the third sample test the answer is  - 1, since during each second at most one candle can burn but Anya needs three candles to light up the room at the moment when the ghost comes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Your story
You've always loved both Fizz Buzz katas and cuckoo clocks, and when you walked by a garage sale and saw an ornate cuckoo clock with a missing pendulum, and a "Beyond-Ultimate Raspberry Pi Starter Kit" filled with all sorts of sensors and motors and other components, it's like you were suddenly hit by a beam of light and knew that it was your mission to combine the two to create a computerized Fizz Buzz cuckoo clock!

You took them home and set up shop on the kitchen table, getting more and more excited as you got everything working together just perfectly. Soon the only task remaining was to write a function to select from the sounds you had recorded depending on what time it was:

## Your plan
* When a minute is evenly divisible by three, the clock will say the word "Fizz".
* When a minute is evenly divisible by five, the clock will say the word "Buzz".
* When a minute is evenly divisible by both, the clock will say "Fizz Buzz", with two exceptions:
  1. On the hour, instead of "Fizz Buzz", the clock door will open, and the cuckoo bird will come out and "Cuckoo" between one and twelve times depending on the hour.
  2. On the half hour, instead of "Fizz Buzz", the clock door will open, and the cuckoo will come out and "Cuckoo" just once. 
* With minutes that are not evenly divisible by either three or five, at first you had intended to have the clock just say the numbers ala Fizz Buzz, but then you decided at least for version 1.0 to just have the clock make a quiet, subtle "tick" sound for a little more clock nature and a little less noise.

Your input will be a string containing hour and minute values in 24-hour time, separated by a colon, and with leading zeros. For example, 1:34 pm would be `"13:34"`.

Your return value will be a string containing the combination of Fizz, Buzz, Cuckoo, and/or tick sounds that the clock needs to make at that time, separated by spaces. Note that although the input is in 24-hour time, cuckoo clocks' cuckoos are in 12-hour time. 

## Some examples
```
"13:34"       "tick"
"21:00"       "Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo"
"11:15"       "Fizz Buzz"
"03:03"       "Fizz"
"14:30"       "Cuckoo"
"08:55"       "Buzz"
"00:00"       "Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo"
"12:00"       "Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo Cuckoo"
```
Have fun!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are three points marked on the coordinate plane. The goal is to make a simple polyline, without self-intersections and self-touches, such that it passes through all these points. Also, the polyline must consist of only segments parallel to the coordinate axes. You are to find the minimum number of segments this polyline may consist of.


-----Input-----

Each of the three lines of the input contains two integers. The i-th line contains integers x_{i} and y_{i} ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9) — the coordinates of the i-th point. It is guaranteed that all points are distinct.


-----Output-----

Print a single number — the minimum possible number of segments of the polyline.


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

Output
1

Input
-1 -1
-1 3
4 3

Output
2

Input
1 1
2 3
3 2

Output
3



-----Note-----

The variant of the polyline in the first sample: [Image] The variant of the polyline in the second sample: $1$ The variant of the polyline in the third sample: $\because$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed graph. The graph is represented as an adjacency matrix of size n*n. Matrix[i][j] denotes the weight of the edge from i to j. If Matrix[i][j]=-1, it means there is no edge from i to j.
Do it in-place.
Example 1:
Input: matrix = {{0,25},{-1,0}}
Output: {{0,25},{-1,0}}
Explanation: The shortest distance between
every pair is already given(if it exists).
Example 2:
Input: matrix = {{0,1,43},{1,0,6},{-1,-1,0}}
Output: {{0,1,7},{1,0,6},{-1,-1,0}}
Explanation: We can reach 2 from 0 as 0->1->2
and the cost will be 1+6=7 which is less than 
43.
Your Task:
You don't need to read, return or print anything. Your task is to complete the function shortest_distance() which takes the matrix as input parameter and modifies the distances for every pair in-place.
Expected Time Complexity: O(n^{3})
Expected Space Complexity: O(1)
Constraints:
1 <= n <= 100
-1 <= matrix[ i ][ j ] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera conducts experiments with algorithms that search for shortest paths. He has recently studied the Floyd's algorithm, so it's time to work with it.

Valera's already written the code that counts the shortest distance between any pair of vertexes in a non-directed connected graph from n vertexes and m edges, containing no loops and multiple edges. Besides, Valera's decided to mark part of the vertexes. He's marked exactly k vertexes a1, a2, ..., ak.

Valera's code is given below.
    
    
      
    ans[i][j] // the shortest distance for a pair of vertexes i, j  
    a[i]  // vertexes, marked by Valera  
      
    for(i = 1; i <= n; i++) {  
        for(j = 1; j <= n; j++) {  
            if (i == j)  
                ans[i][j] = 0;  
            else  
                ans[i][j] = INF;  //INF is a very large number   
        }  
    }      
      
    for(i = 1; i <= m; i++) {  
        read a pair of vertexes u, v that have a non-directed edge between them;  
        ans[u][v] = 1;  
        ans[v][u] = 1;  
    }  
      
    for (i = 1; i <= k; i++) {  
        v = a[i];  
        for(j = 1; j <= n; j++)  
            for(r = 1; r <= n; r++)  
                ans[j][r] = min(ans[j][r], ans[j][v] + ans[v][r]);  
    }  
    

Valera has seen that his code is wrong. Help the boy. Given the set of marked vertexes a1, a2, ..., ak, find such non-directed connected graph, consisting of n vertexes and m edges, for which Valera's code counts the wrong shortest distance for at least one pair of vertexes (i, j). Valera is really keen to get a graph without any loops and multiple edges. If no such graph exists, print -1.

Input

The first line of the input contains three integers n, m, k (3 ≤ n ≤ 300, 2 ≤ k ≤ n , <image>) — the number of vertexes, the number of edges and the number of marked vertexes. 

The second line of the input contains k space-separated integers a1, a2, ... ak (1 ≤ ai ≤ n) — the numbers of the marked vertexes. It is guaranteed that all numbers ai are distinct.

Output

If the graph doesn't exist, print -1 on a single line. Otherwise, print m lines, each containing two integers u, v — the description of the edges of the graph Valera's been looking for.

Examples

Input

3 2 2
1 2


Output

1 3
2 3


Input

3 3 2
1 2


Output

-1

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