akhauriyash/Code-Regression huggingface dataset:
Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k ≥ 1 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a_1, a_2, ..., a_{k} and b_1, b_2, ..., b_{k} satisfying the following requirements:

  k ≥ 1  $\forall i(1 \leq i \leq k) 1 \leq a_{i}, b_{i} \leq|s|$  $\forall i(1 \leq i \leq k) b_{i} \geq a_{i}$  $\forall i(2 \leq i \leq k) a_{i} > b_{i - 1}$  $\forall i(1 \leq i \leq k)$  t is a substring of string s_{a}_{i}s_{a}_{i} + 1... s_{b}_{i} (string s is considered as 1-indexed). 

As the number of ways can be rather large print it modulo 10^9 + 7.


-----Input-----

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 10^5). Each string consists of lowercase Latin letters.


-----Output-----

Print the answer in a single line.


-----Examples-----
Input
ababa
aba

Output
5

Input
welcometoroundtwohundredandeightytwo
d

Output
274201

Input
ddd
d

Output
12

```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 = 's, t = input(), input()\n\nn, m = len(t), len(s) + 1\n\n\n\nd = 1000000007\n\ng = [1] * m\n\n\n\nf = k = 0\n\nfor i in range(1, m):\n\n    if s[i - n:i] == t: k = i\n\n    if k: f = (f + g[k - n]) % d\n\n    g[i] += (g[i - 1] + f) % d\n\n\n\nprint(f)\n\n\n\n\n# Made By Mostafa_Khaled\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13039
A Train started its journey at x=-infinity is travelling on the x-Coordinate Axis. Given n passengers and the coordinates $b_i$ and $d_i$ for each of the $ith$ passenger at which they board and leave from the train respectively. Due to current COVID-19 crisis, the train is monitored at each mile/coordinate. The infection degree of the train at each mile is equal to the total passengers present in the train at that mile/coordinate. The train stops its journey if no more passengers are there to board the train. The term infection severity of the journey is defined as the sum of infection degrees noted at each mile. Find the Infection severity of the journey. Note: A passenger is considered for calculation of infection degree at both boarding and leaving stations.

Since the answer can be very large, print it modulo $(10^9)+7$.

-----Input:-----
- First line will contain $N$, number of passengers. Then the $N$ lines follow. 
- $i$th line contains two integers $b_i, d_i$ , the boarding and departure mile of $i$th passenger.

-----Output:-----
Print a single value, the Infection Severity of the journey modulo $(10^9)+7$.

-----Constraints-----
- $0 \leq N \leq 100000$
- $-500000 \leq b_i \leq 500000$
- $-500000 \leq d_i \leq 500000$

-----Sample Input:-----
3

0 2

1 3

-1 4  

-----Sample Output:-----
12    

-----EXPLANATION:-----
Infection degree at :

-1 is 1

0 is 2

1 is 3

2 is 3

3 is 2

4 is 1

Calculation started at mile -1 and ended at mile 4. Infection Severity = 1+2+3+3+2+1 =12

```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 = 's= 0\r\nn = int(input())\r\nwhile(n):\r\n    \r\n    \r\n    mod = int(1e9+7)\r\n    a,b = [int(x) for x in input().split()]\r\n    s+= abs(b-a) + 1\r\n    s%=mod\r\n    n-=1\r\nprint(s)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12951
There's a **"3 for 2"** (or **"2+1"** if you like) offer on mangoes. For a given quantity and price (per mango), calculate the total cost of the mangoes.

### Examples
```python
mango(3, 3) ==> 6    # 2 mangoes for 3 = 6; +1 mango for free
mango(9, 5) ==> 30   # 6 mangoes for 5 = 30; +3 mangoes for free
```

```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 = 'mango=lambda q,p:q//3*2*p+q%3*p'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'mango'
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: 5302
You are given sequences A and B consisting of non-negative integers.
The lengths of both A and B are N, and the sums of the elements in A and B are equal.
The i-th element in A is A_i, and the i-th element in B is B_i.
Tozan and Gezan repeats the following sequence of operations:
 - If A and B are equal sequences, terminate the process.
 - Otherwise, first Tozan chooses a positive element in A and decrease it by 1.
 - Then, Gezan chooses a positive element in B and decrease it by 1.
 - Then, give one candy to Takahashi, their pet.
Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible.
Find the number of candies given to Takahashi when both of them perform the operations optimally.

-----Constraints-----
 - 1 \leq N \leq 2 × 10^5
 - 0 \leq A_i,B_i \leq 10^9(1\leq i\leq N)
 - The sums of the elements in A and B are equal.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 B_1
:
A_N B_N

-----Output-----
Print the number of candies given to Takahashi when both Tozan and Gezan perform the operations optimally.

-----Sample Input-----
2
1 2
3 2

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

When both Tozan and Gezan perform the operations optimally, the process will proceed as follows:
 - Tozan decreases A_1 by 1.
 - Gezan decreases B_1 by 1.
 - One candy is given to Takahashi.
 - Tozan decreases A_2 by 1.
 - Gezan decreases B_1 by 1.
 - One candy is given to Takahashi.
 - As A and B are equal, the process is terminated.

```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())\nans=0\nc=[]\nfor i in range(n):\n  a,b=map(int,input().split())\n  ans+=a\n  if a>b:c.append(b)\nif len(c):print(ans-min(c))\nelse:print(0)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13037
Well known investigative reporter Kim "Sherlock'' Bumjun needs your help! Today, his mission is to sabotage the operations of the evil JSA. If the JSA is allowed to succeed, they will use the combined power of the WQS binary search and the UFDS to take over the world!
But Kim doesn't know where the base is located. He knows that the base is on the highest peak of the Himalayan Mountains. He also knows the heights of each of the $N$ mountains. Can you help Kim find the height of the mountain where the base is located? 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow.    
- The first line in each testcase contains one integer, $N$.    
- The following $N$ lines of each test case each contain one integer: the height of a new mountain.

-----Output:-----
For each testcase, output one line with one integer: the height of the tallest mountain for that test case.

-----Constraints-----
- $1 \leq T \leq 10$
- $1 \leq N \leq 100000$
- $0 \leq$ height of each mountain $\leq 10^9$

-----Subtasks:-----
- 100 points: No additional constraints.

-----Sample Input:-----
1
5
4
7
6
3
1

-----Sample Output:-----
7

```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())\nfor i in range(t):\n n=int(input())\n a=[]\n for i in range(n):\n  k=int(input())\n  a.append(k)\n print(max(a))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12979
Motu wants to learn Cricket from a coach, but firstly coach wants to test his IQ level, so he gave Motu $1$ $Red$ $ball$ and $1$ $Black$ $ball$ , and asked him to buy other $x – 1$ red balls and other $y – 1$ black balls from the market. But he put some conditions on buying balls, that if he has $R$ red and $B$ black balls then he can either buy $B$ red balls or $R$ black balls in one operation. He can perform this operation as many times as he want. But as Motu is not so good in solving problems so he needs your help. So you have to tell him whether his coach’s task possible or not.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, two integers $x , y$. 

-----Output:-----
For each testcase, print $YES$, if it is possible to complete coach task, else print $NO$(without quotes) in a separate line.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq x, y \leq$ 10^18

-----Sample Input:-----
2
1 2
2 3

-----Sample Output:-----
YES
YES

```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  a,b=list(map(int,input().split()))\n  \n  flag=0\n  while 1:\n      if a==b and a!=1 :\n          print("NO")\n          flag=1\n          break\n        \n      elif a==1 or b==1:\n          print("YES")\n          flag=1\n          break\n        \n      elif a>b and a%b==0:\n          print("NO")\n          flag=1\n          break\n          \n      elif b>a and b%a==0:\n          print("NO")\n          flag=1\n          break\n      \n      if a>b:\n          a,b=a%b,b\n      else:\n          a,b=a,b%a\n \n          \n        \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13175
Iroha has a sequence of N strings S_1, S_2, ..., S_N. The length of each string is L.
She will concatenate all of the strings in some order, to produce a long string.
Among all strings that she can produce in this way, find the lexicographically smallest one.
Here, a string s=s_1s_2s_3...s_n is lexicographically smaller than another string t=t_1t_2t_3...t_m if and only if one of the following holds:

 - There exists an index i(1≦i≦min(n,m)), such that s_j = t_j for all indices j(1≦j<i), and s_i<t_i.
 - s_i = t_i for all integers i(1≦i≦min(n,m)), and n<m.

-----Constraints-----
 - 1 ≦ N, L ≦ 100
 - For each i, the length of S_i equals L.
 - For each i, S_i consists of lowercase letters.

-----Input-----
The input is given from Standard Input in the following format:
N L
S_1
S_2
:
S_N

-----Output-----
Print the lexicographically smallest string that Iroha can produce.

-----Sample Input-----
3 3
dxx
axx
cxx

-----Sample Output-----
axxcxxdxx

The following order should be used: axx, cxx, dxx.

```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,l=map(int,input().split())\ns=sorted([input() for i in range(n)])\nans=""\nfor i in range(n):\n  ans+=s[i]\nprint(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12941
One of Chef's friends offered him a deal: during $D$ days, they are going to exchange money. For each $i$ ($1 \le i \le D$), on the $i$-th day, Chef's friend would give Chef $A$ rupees, while Chef would give his friend $2^{i-1}$ rupees ($1$ rupee on day $1$, $2$ rupees on day $2$, $4$ rupees on day $3$, and so on). Chef's profit from the deal is the total number of rupees he received from his friend minus the total number of rupees he gave his friend.
Chef decided to ask for your advice before accepting the deal. You want to help him by telling him two numbers $D_1$ and $D_2$, where $D_1$ is the maximum value of $D$ such that Chef should accept the deal, i.e. his profit from the deal is positive if $D = D_1$, and $D_2$ is the value of $D$ that leads to the maximum possible profit for Chef. If there are multiple values of $D$ that lead to the maximum profit, $D_2$ is the smallest of these values.

-----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 and only line of each test case contains a single integer $A$.

-----Output-----
For each test case, print a single line containing two space-separated integers $D_1$ and $D_2$.

-----Constraints-----
- $1 \le T \le 100,000$
- $5 \le A \le 10^9$

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

-----Example Input-----
4
5
8
9
1000000000

-----Example Output-----
4 3
5 3
5 4
35 30

```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 a=int(input())\n c=1\n d=1\n ans=[]\n while c<(d*a):\n  ans.append((d*a)-c)\n  c+=2**d\n  d+=1\n t_1=ans.index(max(ans))+1\n print(d-1,t_1,sep=' ')\n "
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13051
In a bizarre game of chess ,knight was so drunk, that instead of his usual move he started walking straight. In every move Knight jumps on 2n steps forward (n is number of block that he had travelled so far from starting) but after that he has to take either 1 step forward or backward.
Now the Knight needs to get to position X so King (i.e. You) needs to decide the order of his backward or forward step in such a way that he can reach its destination in minimum number of steps. Remember he always travels in a straight line and the length of the board is infinite.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases, for each test case enter value X ( i.e. destination)
Note : initially knight is at n = 1.

-----Output-----
For each test case the output should be string of numbers 1 & 2 where 1 denotes backward step and 2 denote the forward step 
Note : for no solution print 0.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ X ≤ 10^10

-----Example-----
Input:
2
17
10
Output:
2111
0

-----Explanation-----
Case 1 : starting from  n = 1 , knight moves to n = 3 ('2') , 5 ('1') , 9 ('1') , 17 ('1') i.e. string printed is 2 1 1 1
Case 2 : no solution is possible

```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 = eval(input())\nfor i in range(t):\n n = eval(input())\n if n%2 == 0:\n  print("0")\n else:\n  s = ""\n  while n>3:\n   if ((n+1)/2)%2==1:\n    s+="1"\n    n = (n+1)/2\n   else:\n    s+="2"\n    n = (n-1)/2\n  print("2"+s[::-1])\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17680
Write a function to split a string and convert it into an array of words. For example:

```python
"Robin Singh" ==> ["Robin", "Singh"]

"I love arrays they are my favorite" ==> ["I", "love", "arrays", "they", "are", "my", "favorite"]
```

```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 string_to_array(s):\n    con = s.split(" ")\n    return con'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'string_to_array'
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: 5568
Chef and Chefina are best friends. Chefina wants to test the Problem Solving skills of chef so she provides Chef 2 integer number  $X$ and $Y$
The task of chef is to take the  two numbers $X$ and $Y$ and return their SUM.
Identify whether Chef can solve the problem or not? 

-----Input:-----
- First line will contain the two integers $X$ and $Y$.

-----Output:-----
For each testcase, output in a single line the SUM of these two numbers $X$ and $Y$.

-----Constraints-----
- $1 \leq X \leq 100$
- $1 \leq Y \leq 100$

-----Sample Input:-----
6 70

-----Sample Output:-----
76

```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\nX ,Y = map(int, input().split())\noutput = X + Y\nprint(output)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12829
Andrii is good in Math, but not in Programming. He is asking you to solve following problem: Given an integer number N and two sets of integer A and B. Let set A contain all numbers from 1 to N and set B contain all numbers from N + 1 to 2N. Multiset C contains all sums a + b such that a belongs to A and b belongs to B. Note that multiset may contain several elements with the same values. For example, if N equals to three, then A = {1, 2, 3}, B = {4, 5, 6} and C = {5, 6, 6, 7, 7, 7, 8, 8, 9}. Andrii has M queries about multiset C. Every query is defined by a single integer q. Andrii wants to know the number of times q is contained in C. For example, number 6 is contained two times, 1 is not contained in C at all. 

Please, help Andrii to answer all the queries.

-----Input-----

The first line of the input contains two integers N and M. Each of the next M line contains one integer q, the query asked by Andrii.

-----Output-----
Output the answer for each query in separate lines as in example.

-----Constraints-----
- 1 ≤ N ≤ 109
- 1 ≤ M ≤ 105
- 1 ≤ q ≤ 3N

-----Example-----
Input:
3 5
6
2
9
7
5
Output:
2
0
1
3
1

```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\nn,m = list(map(int,input().split(" ")))\nfor i in range(m):\n    q = int(input())\n    if(q<n+2):\n        print(\'0\')\n        continue\n    else:\n        print(n-abs(2*n +1 -q))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13013
Given an array A1,A2...AN, you have to print the size of the largest contiguous subarray such that 
GCD of all integers in that subarray is 1.

Formally,
For a subarray Ai,Ai+1...Aj where 1 ≤ i < j ≤ N to be valid: GCD(Ai,Ai+1...Aj) should be 1. You have to print the size of the largest valid subarray.
If no valid subarray exists, output -1.
Note:A single element is not considered as a subarray according to the definition of this problem.

-----Input-----
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in the next line.

-----Output-----
For each testcase, print the required answer in one line.

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

-----Example-----
Input:
2
2
7 2
3
2 2 4

Output:
2
-1

-----Explanation-----
Example case 1.GCD(2,7)=1. So the subarray [A1,A2] is valid.
Example case 2.No subarray satisfies.
Note: Use scanf/print instead of cin/cout. Large input files.

```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 = 'from math import gcd\nfor t in range(int(input())):\n n=int(input())\n a=sorted(set(int(i) for i in input().split()))\n l=len(a)\n for j in range(l-1):\n  if gcd(a[j], a[j+1]) == 1:\n   print(n)\n   break\n else:\n  print(-1)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13129
Ask a small girl - "How old are you?". She always says strange things... Lets help her!


For correct answer program should return int from 0 to 9.

Assume test input string always valid and may look like 
"1 year old" or "5 years old", etc.. The first char is number only.

```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 = 'get_age=lambda s:int(s[0])'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'get_age'
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: 5304
# Rock Paper Scissors

Let's play! You have to return which player won! In case of a draw return `Draw!`.

Examples:

![rockpaperscissors](http://i.imgur.com/aimOQVX.png)

```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 rps(p1, p2):\n    d= {'scissors': 'paper', 'rock': 'scissors', 'paper': 'rock'}\n    return 'Draw!' if p1 == p2 else 'Player 1 won!' if d[p1] == p2 else 'Player 2 won!'\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'rps'
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: 5506
This is probably the simplest problem ever. You just need to count the number of ordered triples of different numbers (X1, X2, X3), where Xi could be any positive integer from 1 to Ni, inclusive (i = 1, 2, 3).
No, wait. I forgot to mention that numbers N1, N2, N3 could be up to 1018. Well, in any case it is still quite simple :)
By the way, because of this the answer could be quite large. Hence you should output it modulo 109 + 7. That is you need to find the remainder of the division of the number of required triples by 109 + 7.

-----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 only line of each test case contains three space-separated integers N1, N2, N3.

-----Output-----
For each test case, output a single line containing the number of required triples modulo 109 + 7.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ Ni ≤ 1018

-----Example-----
Input:
5
3 3 3
2 4 2
1 2 3
25 12 2012
1 1 2013

Output:
6
4
1
578880
0

-----Explanation-----
Example case 1. We have the following triples composed of different numbers up to 3:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
Example case 2. Here the triples are:
(1, 3, 2)
(1, 4, 2)
(2, 3, 1)
(2, 4, 1)
Example case 3. Here the only triple is (1, 2, 3).
Example case 4. Merry Christmas! 
Example case 5. ... and Happy New Year! By the way here the answer is zero since the only choice for X1 and for is X2 is 1, so any such triple will have equal numbers.

```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 = list(map(int, input().split()))\n N.sort()\n N1, N2, N3 = N[0], N[1], N[2]\n M = 10**9 + 7\n ans = ((((N1 % M) * ((N2-1) % M)) % M) * (N3-2) % M) % M\n print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13069