akhauriyash/Code-Regression huggingface dataset:
Chef and Roma are playing a game. Rules of the game are quite simple.
Initially there are N piles of stones on the table.
In each turn, a player can choose one pile and remove it from the table.
Each player want to maximize the total number of stones removed by him.
Chef takes the first turn. 

Please tell Chef the maximum number of stones he can remove assuming that both players play optimally.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of piles.
The second line contains N space separated integers A1, A2, ..., AN denoting the number of stones in each pile.

-----Output-----
For each test case, output a single line containg the maximum number of stones that Chef can remove.

-----Constraints-----
- 1 ≤ Ai ≤ 109
- Subtask 1 (35 points): T = 10, 1 ≤ N ≤ 1000
- Subtask 2 (65 points): T = 10, 1 ≤ N ≤ 105 

-----Example-----
Input:
2
3
1 2 3
3
1 2 1

Output:
4
3

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for _ in range(int(input())):\n n = int(input())\n array = [int(i) for i in input().split()]\n array.sort()\n\n stones1 = sum([array[i] for i in range(0, n, 2)])\n stones2 = sum([array[i] for i in range(1, n, 2)])\n print(max(stones2, stones1)) '
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13133
Chef has provided with a sequence of integers of length $N$ arranged in an unsorted fashion.
The elements of the sequence are ordered as ${A1,A2,A3.....A'N}$
The task of the chef is to identify the highest and lowest value among the given sequence. It is assured that the sequence given contains the highest and the lowest value always
Please help chef in finding the desired value.

-----Input:-----
- First line will contain $N$, number of elements in the sequence.  
- Next line contains  $N$ integers of the sequence  . 

-----Output:-----
Print the HIGHEST and  LOWEST value of the sequence respectively.

-----Constraints-----
- $1 \leq N \leq 100$
- $2 \leq  {A1,A2,A3.....A'N}  \leq 10^4$

-----Sample Input:-----
5
3 2 7 9 4

-----Sample Output:-----
9 2

-----EXPLANATION:-----
This list is :
[3,2,7,9,4]  so the highest value is 9 and lowest is 2 respectively.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish her\nN = int(input())\narr = list(map(int , input().split()))\nprint(max(arr) , min(arr))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12923
Raju has created a program to find the square root of a number. But his program can store only integers. Being a newbie, he didn't know about rounding the numbers. Hence his program returns the absolute value of the result if possible. For example, sqrt(3) = 1.73205080757……. His program will return 1
Given a number $N$, and it's integral square root $S$, His instructor will consider the answer correct if Difference between $N$ and the square of $S$ is within less than or equal to $X$% of $N$.

-----Input:-----
- First line contains $T$ no. of test cases and $X$ separated by space
- For every test case, a line contains an integer $N$

-----Output:-----
For every test case, print yes  if his programs return square root and (N-(S^2)) <= 0.01XN . For everything else, print no on a new line

-----Constraints-----
10 points:
- $1 \leq T \leq 10$
- $0\leq N \leq 10$
20 points:
- $1 \leq T \leq 30000$
- $-10^9 \leq N \leq 10^9$
70 points:
- $1 \leq T \leq 10^6$
- $-10^9 \leq N \leq 10^9$

-----Sample Input:-----
2 20
5
3

-----Sample Output:-----
yes
no

-----EXPLANATION:-----
In #1, sqrt(5) = 2.2360679775. Taking integral value, S = 2.

S2 = 4. Difference=1 which is within 20% of 5
In #1, sqrt(3) = 1.73205080757. Taking integral value, S = 1.

S2 = 1. Difference=2  which is not within 20% of 3

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import math\nt,n =input().split()\nt=int(t)\nn=int(n)\n\nfor _ in range(t):\n num=eval(input())\n num=int(num)\n #print("num",num)\n sq=int(math.sqrt(num))\n #print("sq",sq)\n squ=sq**2\n #print("squ",squ)\n diff=0.01*n*num\n #print("diff",diff)\n \n if (num-squ)<=diff:\n  print("yes")\n else:\n  print("no")\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17540
Almir had a small sequence $A_1, A_2, \ldots, A_N$. He decided to make $K$ copies of this sequence and concatenate them, forming a sequence $X_1, X_2, \ldots, X_{NK}$; for each valid $i$ and $j$ ($0 \le j < K$), $X_{j \cdot N + i} = A_i$.
For example, if $A = (1, 2, 3)$ and $K = 4$, the final sequence is $X = (1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3)$.
A pair $(i, j)$, where $1 \le i < j \le N$, is an inversion if $X_i > X_j$. Find the number of inversions in the final sequence $X$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of inversions in the sequence $X$.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 100$
- $1 \le K \le 10^6$
- $1 \le A_i \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
3 3
2 1 3
4 100
99 2 1000 24

-----Example Output-----
12
30000

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nfor _ in range(int(eval(input()))):\n    n, k = list(map(int, input().split()))\n    arr = list(map(int, input().split()))\n    x, suffix = 0, 0\n    for i, a_i in enumerate(arr):\n        for a_j in arr:\n            if a_i > a_j: x += 1\n        for j in range(i+1, n):\n            if a_i > arr[j]: suffix += 1\n            \n    ans = x*( (k*(k-1))//2 ) + suffix*k\n    print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16877
Write a program to find the remainder when an integer A is divided by an integer B.

-----Input-----

The first line contains an integer T, the total number of test cases. Then T lines follow, each line contains two Integers A and B. 

-----Output-----
For each test case, find the remainder when A is divided by  B, and display it in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ A,B ≤ 10000

-----Example-----
Input
3 
1 2
100 200
40 15

Output
1
100
10

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't = int(input())\r\nfor i in range(t):\r\n    c , d = input().split()\r\n    a = int (c) \r\n    b = int (d)\r\n    print(a%b)\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12915
Chef Jessie has a lot of recipes with her (N). She often remembered the starting few characters of the recipe and forgot the rest. As all the great chefs do, Jessie also numbered the recipes depending on the priority. So, given the list of recipes along with their priorities answer Jessie’s queries.
Jessie’s queries are as follows:

She gives you the first few characters of a recipe; you have to print the complete recipe with the highest priority.
Note:

Every recipe has a unique priority

-----Input-----

First line contains an integer N - the number of recipes.

Followed by N strings Si along with an integer each Vi.
Si stands for the recipe and Vi for the priority.

It is followed by an integer Q - the number of queries.

Followed by Q strings Qi.

Each string Si, Qi contain only lowercase Latin alphabets ('a' - 'z') and '-'.

-----Output-----
Q – lines, each contain the answer for each of the query.

If for a query no recipe matches print "NO". (Without quotes)
Constraints:
0 <= N <= 1000

0 <= Q <= 1000

-10^9 <= Vi <= 10^9

1 <= |Si| <= 1000 (length of Si)

1 <= |Qi| <= 1000 (length of Qi)

-----Example-----
Input:
4
flour-with-eggs 100
chicken-ham -10
flour-without-eggs 200
fish-with-pepper 1100
6
f
flour-with
flour-with-
c
fl
chik

Output:
fish-with-pepper
flour-without-eggs
flour-with-eggs
chicken-ham
flour-without-eggs
NO

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nimport re\nn=int(input())\nl=[]\nfor _ in range(n):\n l.append(input().split())\n l[-1][1]=int(l[-1][1])\n \nl.sort(key=lambda x: x[1], reverse=True)\nq=int(input())\nfor _ in range(q):\n \n s="^"+input()\n \n for k in l:\n  if re.findall(s, k[0]):\n   print(k[0])\n   break\n else:\n  print(\'NO\')\n \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 33678
Determine the total number of digits in the integer (`n>=0`) given as input to the function. For example, 9 is a single digit, 66 has 2 digits and 128685 has 6 digits. Be careful to avoid overflows/underflows.

All inputs will be valid.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def digits(n):\n    s = str(n)\n    return len(s)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'digits'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5322
Ho, Ho, Ho!
It's Christmas time and our friendly grandpa Santa Claus is busy distributing gifts to all the nice children. With the rising population, Santa's workload every year gets increased and he seeks your help to wrap the gifts with fancy wrapping papers while he gets them distributed. 
Everything was going great until you realised that you'll fall short of wrapping paper. But luckily, you get a very innovative idea, that will allow you to pack all the remaining gifts without worrying about lack of wrapping paper. Any guesses what the idea is? Using ice for wrapping, obviously! That's the only thing available at the North Pole.
Now, in order to reduce your trips to the ice factory, you decide to write a program that helps you visualize how much ice is needed for a particular gift. 

-----Input:-----
Input will consist of a single line with size $n$.

-----Output:-----
Print the ice wrapped gift box for the given size. 

-----Constraints-----
- $0 \leq n \leq 1000$

-----Sample Input:-----
4

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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n=int(input())\r\na=[]\r\nsize=(2*n)-1\r\nb=[n]*size\r\nsize-=2\r\ncurr=n-1\r\na.append(b)\r\nfor i in range(n-1):\r\n    c=b.copy()\r\n    c[i+1:i+1+size]=[curr]*size\r\n    a.append(c)\r\n    b=c.copy()\r\n    curr-=1\r\n    size-=2\r\nfor i in range(len(a)):\r\n    print(*a[i])\r\nfor i in range(len(a)-2,-1,-1):\r\n    print(*a[i])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13217
You've got array A, consisting of n integers and a positive integer k. Array A is indexed by integers from 1 to n.

You need to permute the array elements so that value $\sum_{i = 1}^{n - k}|A [ i ] - A [ i + k ]|$ became minimal possible. In particular, it is allowed not to change order of elements at all.


-----Input-----

The first line contains two integers n, k (2 ≤ n ≤ 3·10^5, 1 ≤ k ≤ min(5000, n - 1)). 

The second line contains n integers A[1], A[2], ..., A[n] ( - 10^9 ≤ A[i] ≤ 10^9), separate by spaces — elements of the array A.


-----Output-----

Print the minimum possible value of the sum described in the statement.


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

Output
1

Input
5 2
3 -5 3 -5 3

Output
0

Input
6 3
4 3 4 3 2 5

Output
3



-----Note-----

In the first test one of the optimal permutations is 1 4 2. 

In the second test the initial order is optimal. 

In the third test one of the optimal permutations is 2 3 4 4 3 5.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def solve(n, k, As):\n    As.sort()\n    m, r = divmod(n, k)\n    dp = [0] * (r + 1)\n    for i in range(1, k):\n        im = i * m\n        new_dp = [0] * (r + 1)\n        new_dp[0] = dp[0] + As[im] - As[im - 1]\n        for h in range(1, min(i, r) + 1):\n            new_dp[h] = max(dp[h], dp[h - 1]) + As[im + h] - As[im + h - 1]\n        dp = new_dp\n    return As[-1] - As[0] - max(dp[r], dp[r-1])\n\nn, k = map(int, input().split())\nAs = list(map(int, input().split()))\nprint(solve(n, k, As))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13109
Chef loves to play with arrays by himself. Today, he has an array A consisting of N distinct integers. He wants to perform the following operation on his array A.

- Select a pair of adjacent integers and remove the larger one of these two. This decreases the array size by 1. Cost of this operation will be equal to the smaller of them.

Find out minimum sum of costs of operations needed to convert the array into a single element.

-----Input-----
First line of input contains a single integer T denoting the number of test cases. First line of each test case starts with an integer N denoting the size of the array A. Next line of input contains N space separated integers, where the ith integer denotes the value Ai.

-----Output-----
For each test case, print the minimum cost required for the transformation.

-----Constraints-----
- 1 ≤ T ≤ 10 
- 2 ≤ N ≤ 50000 
- 1 ≤ Ai ≤ 105 

-----Subtasks-----
- Subtask 1 : 2 ≤ N ≤ 15 : 35 pts 
- Subtask 2 : 2 ≤ N ≤ 100 : 25 pts 
- Subtask 3 : 2 ≤ N ≤ 50000 : 40 pts 

-----Example-----
Input
2
2
3 4
3
4 2 5

Output
3
4

-----Explanation-----Test 1 :  Chef will make only 1 move: pick up both the elements (that is, 3 and 4), remove the larger one (4), incurring a cost equal to the smaller one (3).

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for _ in range(int(input())):\n n=int(input())\n a=list(map(int,input().split()))\n m=min(a)\n print(m*(n-1))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12989
Little Praneet loves experimenting with algorithms and has devised a new algorithm. The algorithm is performed on an integer as follows:
- if the rearmost digit is $0$, he will erase it.
- else, he will replace the rearmost digit $d$ with $d-1$.
If a point comes when the integer becomes $0$, the algorithm stops.
You are given an integer $n$. Praneet will perform the algorithm on it $a$ times. You have to print the result after $a$ operations.

-----Input:-----
- The first and only line of input contains two integers $n$ — initial number, and $a$ —the number of operations.

-----Output:-----
- Print one integer — the result of performing the algorithm on $n$ $a$ times.

-----Constraints-----
- $2 \leq n \leq 10^9$
- $1 \leq a \leq 50$

-----Sample Input 1-----
1001 2

-----Sample Input 2-----
5 2

-----Sample Output 1-----
100

-----Sample Output 2-----
3

-----Explanation-----
- In the first example, the transformation is as follows: $1001->1000->100$.
- In the second example, the transformation is as follows: $5->4->3$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '#q1\nn,x=list(map(int,input().split()))\nfor i in range(x):\n if(n==0):\n  break\n if(n%10==0):\n  n=n//10\n else:\n  n-=1\nprint(n)\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12937
When provided with a String, capitalize all vowels

For example:

Input : "Hello World!"

Output : "HEllO WOrld!"

Note: Y is not a vowel in this kata.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def swap(st):\n  tr = str.maketrans('aeiou', 'AEIOU')\n  return st.translate(tr);"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'swap'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5482
Given an Integer N, write a program to reverse it.

-----Input-----

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N. 

-----Output-----
For each test case, display the reverse of the given number N, in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 1000000

-----Example-----
Input
4
12345
31203
2123
2300
Output
54321
30213
3212
32

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nfor I in range(int(input())):\n      num=int(input())\n      rev=0\n      while num!=0:\n        rev=(rev*10)+(num%10)\n        num=num//10\n      print(rev)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12905
-----General Statement:-----
Read a number in scientific notation and output its equivalent decimal value.

-----Input:-----
All data is on a single line. The first integer indicates how many pairs of numbers follow. The first of each pair is A, the base number, and the second is E, the power of 10.

-----Output:-----
Round each answer to 2 decimal places. Trailing zeros to the right of the decimal point are required. A leading zero to the left of the decimal point is not required.
The output is to be formatted exactly like that for the sample output given below.

-----Assumptions:-----
E is in the range –10 .. 10. A is 1 or larger but less than 10.
Discussion: 
If A = 3.926 and E = 4, the number represented is 3.926 X 104 or 39260, which is 39260.00 when rounded to 2 decimal places.

-----Sample Input:-----
4 4.296 3 3.8 -2 1.8 2 2.8678 1

-----Sample Output:-----
4296.00
0.04
180.00
28.68

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'a = list(map(float,input().split()))\r\nfor i in range(int(a[0])):\r\n    print("%0.2f"%(a[(2*i)+1]*(10**a[(2*i)+2])))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12987
Igor the analyst has adopted n little bunnies. As we all know, bunnies love carrots. Thus, Igor has bought a carrot to be shared between his bunnies. Igor wants to treat all the bunnies equally, and thus he wants to cut the carrot into n pieces of equal area. 

Formally, the carrot can be viewed as an isosceles triangle with base length equal to 1 and height equal to h. Igor wants to make n - 1 cuts parallel to the base to cut the carrot into n pieces. He wants to make sure that all n pieces have the same area. Can you help Igor determine where to cut the carrot so that each piece have equal area?

 [Image] Illustration to the first example. 


-----Input-----

The first and only line of input contains two space-separated integers, n and h (2 ≤ n ≤ 1000, 1 ≤ h ≤ 10^5).


-----Output-----

The output should contain n - 1 real numbers x_1, x_2, ..., x_{n} - 1. The number x_{i} denotes that the i-th cut must be made x_{i} units away from the apex of the carrot. In addition, 0 < x_1 < x_2 < ... < x_{n} - 1 < h must hold. 

Your output will be considered correct if absolute or relative error of every number in your output doesn't exceed 10^{ - 6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
1.154700538379 1.632993161855

Input
2 100000

Output
70710.678118654752



-----Note-----

Definition of isosceles triangle: https://en.wikipedia.org/wiki/Isosceles_triangle.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n, h = map(int, input().split())\ns = \'\'\nfor i in range(1, n):\n\ts += "%.6f " % (i * h * h / n) ** 0.5\nprint(s)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12893
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

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

-----Sample Output:-----
12
21
123
231
312
1234
2341
3412
4123

-----EXPLANATION:-----
No need, else pattern can be decode easily.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for _ in range(int(input())):\n    n = int(input())\n    l = list(range(1, n + 1))\n    for x in range(n):\n        print(*l[x:], sep="", end="")\n        print(*l[:x], sep="")\n# cook your dish here\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12981
We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N.
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M).
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:
 - Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.
Find the maximum possible number of i such that p_i = i after operations.

-----Constraints-----
 - 2 ≤ N ≤ 10^5
 - 1 ≤ M ≤ 10^5
 - p is a permutation of integers from 1 through N.
 - 1 ≤ x_j,y_j ≤ N
 - x_j ≠ y_j
 - If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

-----Output-----
Print the maximum possible number of i such that p_i = i after operations.

-----Sample Input-----
5 2
5 3 1 4 2
1 3
5 4

-----Sample Output-----
2

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'n,m=list(map(int,input().split()))\na=list(map(int,input().split()))\ns=[[] for i in range(n)]\nfor i in range(m):\n  inp=list(map(int,input().split()))\n  s[inp[0]-1].append(inp[1]-1)\n  s[inp[1]-1].append(inp[0]-1)\nc=0\nd=[0 for i in range(n)]\nfor i in range(n):\n  if d[i]:\n    continue\n  c+=1\n  d[i]=c\n  st=s[i]\n  while st:\n    ns=[]\n    for j in st:\n      if d[j]:\n        continue\n      d[j]=c\n      ns+=s[j]\n    st=ns\nc=0\nfor i in range(n):\n  if d[i]==d[a[i]-1]:\n    c+=1\nprint(c)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13599