Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np

N = int(input())

for n in range(1, N + 1):
    cnt = 0
    th = int(np.sqrt(n)) + 1
    for x in range(1, th):
        thy = int(np.sqrt(n - x ** 2)) + 1
        for y in range(1, thy):
            try:
                thz = int(np.sqrt(n - x ** 2 - y ** 2 - x * y)) + 1
            except ValueError:
                break
            for z in range(1, thz):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

import numpy as np

N = int(input())
res = np.zeros(N+1)

th = int(np.sqrt(N)) + 1
for x in range(1, th):
    for y in range(1, x + 1):
        for z in range(1, y + 1):
            n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if n > N:
                continue
            if x == y and y == z:
                res[n] += 1
            elif x == y or y == z or z == x:
                res[n] += 3
            else:
                res[n] += 6
for i in range(1, N+1):
    print(int(res[i]))
### BUGGY CODE ###

a, b, k = map(int,input().split())
for n in range(a, b+1):
    if n <= a+k-1 or n >= b-k+1:
        print(n)

### FIXED CODE ###

a, b, k = map(int,input().split())
if 2*k > b - a + 1:
    for n in range(a, b+1):
        print(n)
    exit()
for n in range(a, a+k):
    print(n)
for n in range(b-k+1, b+1):
    print(n)
### BUGGY CODE ###

h, w = map(int, input().split())

s = [input() for _ in range(h)]

x_inf = [[0 for i in range(w)] for j in range(h)]
y_inf = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    p = -1
    for j in range(w):
        if s[i][j]=="#":
            p = j
        else:
            x_inf[i][j] = p

for i in range(h):
    p = w
    for j in range(-1,-w-1,-1):
        if s[i][j]=="#":
            p = w+j
        else:
            x_inf[i][j] -= p-1

for i in range(w):
    p = -1
    for j in range(h):
        if s[j][i]=="#":
            p = j
        else:
            y_inf[j][i] = p

for i in range(w):
    p = h
    for j in range(h-1,-1,-1):
        if s[j][i]=="#":
            p = j
        else:
            y_inf[j][i] -= p-1
result = []
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            result.append(x_inf[i][j]+y_inf[i][j]+1)
print(-min(result))

### FIXED CODE ###

h, w = map(int, input().split())

s = [input() for _ in range(h)]

x_inf = [[0 for i in range(w)] for j in range(h)]
y_inf = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    p = -1
    for j in range(w):
        if s[i][j]=="#":
            p = j
        else:
            x_inf[i][j] = p

for i in range(h):
    p = w
    for j in range(-1,-w-1,-1):
        if s[i][j]=="#":
            p = w+j
        else:
            x_inf[i][j] -= p-1

for i in range(w):
    p = -1
    for j in range(h):
        if s[j][i]=="#":
            p = j
        else:
            y_inf[j][i] = p

for i in range(w):
    p = h
    for j in range(h-1,-1,-1):
        if s[j][i]=="#":
            p = j
        else:
            y_inf[j][i] -= p-1
result = []
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            result.append(x_inf[i][j]+y_inf[i][j]+1)
print(-min(result))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)


def check(i, xs):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs):
            return False
    return True


def solve():
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs)
            if not res:
                return False
            xf = list(filter(lambda x: x is not None, xs))
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
checked = set()
print('Yes' if solve() else 'No')


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if checked[j]:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked[i] = True
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            mn, mx = min(xs.values()), max(xs.values())
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')
### BUGGY CODE ###

L, R = map(int, input().split())

idx1 = 0
listA = []
for idx1 in range(L, R):
  for idx2 in range(idx1 + 1, R + 1):
    listA.append(idx1 * idx2)

idx3 = 0
listB = []
for idx3 in range(len(listA)):
  listB.append(listA[idx3] % 2019)

print(min(listB))

### FIXED CODE ###

L, R = map(int, input().split())

listX = []
for i in range(1, 990590):
  listX.append(i*2019)

sw = 0
for n in range(len(listX)):
  if L < listX[n] and R > listX[n]:
    sw += 1

if sw > 0:
  print(0)

elif sw == 0:
  idx1 = 0
  listA = []
  for idx1 in range(L, R):
    for idx2 in range(idx1 + 1, R + 1):
      listA.append(idx1 * idx2)
 
  idx3 = 0
  listB = []
  for idx3 in range(len(listA)):
    listB.append(listA[idx3] % 2019)
 
  print(min(listB))
### BUGGY CODE ###

from collections import defaultdict
N, P = map(int,input().split())
S = input()
if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    primdic = defaultdict(int)
    for i in range(N):
        primdic[int(S[i:])%P] += 1
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = S[::-1]
    primdic = defaultdict(int)
    before = 0
    for i in range(0,N):
        now = (int(S[i])*pow(10,i,P)+before)%P
        primdic[now] += 1
        before = now
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
    w,v = wv[i-1]
    for j in range(1,W+1):
        if j >= w:
            DP[i][j] = max(DP[i-1][j],DP[i][j-1],DP[i-1][j-w]+v)
        else:
            DP[i][j] = max(DP[i-1][j],DP[i][j-1])
print(DP[-1][-1])

### FIXED CODE ###

N,W = map(int,input().split())
wv = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    w,v = wv[i]
    for j in range(1,W+1):
        if j >= w:
            DP[i+1][j] = max(DP[i][j-w]+v,DP[i][j],DP[i+1][j-1])
        else:
            DP[i+1][j] = max(DP[i][j],DP[i+1][j-1])
print(DP[-1][-1])
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def dfs(n, g, v, seen):
    seen[v] = True

    for nv in range(n):
        if g[v][nv][0]:
            if seen[nv]:
                continue
            dfs(n, g, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())
    ab = [list(map(int, stdin.readline().split())) for _ in range(m)]
    cd = [list(map(int, stdin.readline().split())) for _ in range(k)]

    g = [[[False, False] for _ in range(n)] for _ in range(n)]

    for a, b in ab:
        g[a - 1][b - 1][0] = True
        g[b - 1][a - 1][0] = True

    for c, d in cd:
        g[c - 1][d - 1][1] = True
        g[d - 1][c - 1][1] = True

    ans = [0] * n
    for i in range(n):
        seen = [False] * n
        dfs(n, g, i, seen)
        for j in range(n):
            if g[i][j][0] == False and g[i][j][1] == False and i != j and seen[j]:
                ans[i] += 1

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0:
            x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        p = self.parent
        if x != y:
            x, y = sorted([x, y])
            p[x], p[y] = p[x] + p[y], x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parent[self.find(x)]


def main():
    n, m, k = map(int, stdin.readline().split())

    f = UnionFindTree(n)

    f_or_b = [0] * n

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f.union(a - 1, b - 1)
        f_or_b[a - 1] += 1
        f_or_b[b - 1] += 1

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        if f.same(c - 1, d - 1):
            f_or_b[c - 1] += 1
            f_or_b[d - 1] += 1

    print(*[f.size(i) - f_or_b[i] - 1 for i in range(n)])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**9)
#import
#import math
#import numpy as np
N = int(input())
A = list(map(int, input().split()))

dp = [[-1] * (N + 1) for _ in range(N + 1)]

# 半開区間A[r,l)における最大スコア
def calc(r, l):
    if dp[r][l] != -1:
        return dp[r][l]

    if l - r == 1:
        dp[r][l] = A[r]
        return dp[r][l]

    elif l - r == 2:
        dp[r][l] = max(A[r], A[r + 1]) - min(A[r], A[r + 1])
        return dp[r][l]

    res = max(A[r] - calc(r + 1, l), A[l - 1] - calc(r, l - 1))
    dp[r][l] = res
    return res

ans = calc(0, N)

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**9)
#import
#import math
#import numpy as np
N = int(input())
A = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(N + 1)]


for w in range(1, N + 1):
    for l in range(N - w + 1):
        r = w + l
        dp[l][r] = A[l] - dp[l + 1][r]
        if r > 0:
            dp[l][r] = max(dp[l][r], A[r - 1] - dp[l][r - 1])

print(dp[0][N])
### BUGGY CODE ###

s = input()

sl = list(s)
sl.append("2")

n = len(sl)
res=[]

temp =1
for i  in range(n-1):
    if sl[i+1] == sl[i]:
        temp +=1
    else:
        res.append(temp)
        temp = 1

resu = n-1

while len(res) >1:
    resu = min(resu,max(res[0],sum(res[1:])))
    x = res.pop(1)
    res[0]  = res[0]+x    
    
print(resu)

### FIXED CODE ###

s = input()

sl = list(s)
sl.append("2")

n = len(sl)
res=[]

temp =1
for i  in range(n-1):
    if sl[i+1] == sl[i]:
        temp +=1
    else:
        res.append(temp)
        temp = 1

resu = n-1
m = n-1

while len(res) >1:
    resu = min(resu,max(res[0],m-res[0]))
    x = res.pop(1)
    res[0]  = res[0]+x    
    
print(resu)
### BUGGY CODE ###

s = input()
rev = False
for _ in range(int(input())):
  t = input()
  if t == "1":
    rev = not rev
  else:
    t = t.split()
    if (t[1] == "1" and not rev) or (t[1] == "2" and rev):
      s = t[2] + s
    else:
      s += t[2]
if rev:
  for i in reversed(s):
    print(i, end="")
else:
  print(s)


### FIXED CODE ###

S = input()
len_s = len(S)
rev = False
max_ = 2*10**5
index = max_ + len_s
rev_index = max_ - 1
s = ["." for _ in range(max_*2 + len_s)]
for i in range(len_s):
    s[max_+i] = S[i]
for _ in range(int(input())):
  t = input()
  if t == "1":
    rev = not rev
  else:
    t = t.split()
    if (t[1] == "1" and not rev) or (t[1] == "2" and rev):
      s[rev_index] = t[2]
      rev_index -= 1
    else:
      s[index] = t[2]
      index += 1
if rev:
  for i in range((max_ + max_ + len_s - 1), 0, -1):
    if s[i] != ".":
      print(s[i], end="")
else:
  for i in range((max_ + max_ + len_s)):
    if s[i] != ".":
      print(s[i], end="")
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    from collections import deque
    divisors = deque([])
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.appendleft(num)
    return list(divisors)

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))

# nの約数を求める。計算量O(sqrt(N))
def get_divisors(n):
    from math import sqrt, ceil
    from collections import deque
    divisors = deque([])
    for num in range(ceil(sqrt(n)), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.appendleft(num)
    return list(divisors)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = make_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)
### BUGGY CODE ###

n, m = map(int, input().split())
a_s = list(map(int, input().split()))

for i in range(m):
	a_s = sorted(a_s)
	a_s[-1] = a_s[-1] // 2

res = sum(a_s)
print(res)


### FIXED CODE ###

from math import ceil
from heapq import *

n, m = map(int, input().split())
a_s = [-int(a) for a in input().split()]
heapify(a_s)

for _ in range(m):
	amax = heappop(a_s)
	heappush(a_s, ceil(amax / 2))

res = sum([-heappop(a_s) for _ in range(n)])
print(res)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    S = input()
    Q = int(input())
    Query = [input().split() for _ in range(Q)]

    S_deque = deque()
    for s in S:
        S_deque.append(s)

    for q in Query:
        if q[0]=='1':
            S_deque.reverse()
        elif q[0]=='2':
            if q[1]=='1':
                S_deque.appendleft(q[2])
            elif q[1]=='2':
                S_deque.append(q[2])

    print(*S_deque, sep='')

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    S = input()
    Q = int(input())
    Query = [input().split() for _ in range(Q)]

    S_deque = deque()
    for s in S:
        S_deque.append(s)
 
    is_reversed = False
    for q in Query:
        if q[0]=='1':
            is_reversed = not is_reversed
        elif q[0]=='2':
            if (not is_reversed and q[1]=='1') or (is_reversed and q[1]=='2'):
                S_deque.appendleft(q[2])
            else:
                S_deque.append(q[2])

    if is_reversed:
        S_deque.reverse()

    print(*S_deque, sep='')

if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

ans = 0

num_array = [0] * N
for i in range(N):
    num_array[i] = (p[i]+1) / 2

ans = sum(num_array[0:K])    
for i in range(1, N-K+1):
    temp = sum(num_array[i:i+K])
    if temp > ans:
        ans = sum(num_array[i:i+K])

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

ans = 0

num_array = [0] * N
for i in range(N):
    num_array[i] = (p[i]+1) / 2

ans = sum(num_array[0:K])
temp = ans
for i in range(1, N-K+1):
    j = i+K-1
    temp = temp - num_array[i-1] + num_array[j]
    if temp > ans:
        ans = temp

print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

f_inf = float('inf')

dp = [f_inf] * (10**5+10)

dp[0] = 0
for i in range(1, n):
    for j in range(1, k+1):
        if i - j >= 0:
            dp[i] = chmin(dp[i], dp[i-j]+ abs(h[i] - h[i - j]))

print(dp[n-1])


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

f_inf = float('inf')
dp = np.zeros(n, dtype=int)
h = np.array(h)
for i in range(1, n):
    start = max(0, i - k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

N = list(map(int, input().split()))[-1]
A = sorted(list(map(int, input().split())))[::-1][:N]
B = sorted(list(map(int, input().split())))[::-1][:N]
C = sorted(list(map(int, input().split())))[::-1][:N]

result = [A[i]+B[j]+C[k] 
          for i in range(len(A)) 
          for j in range(len(B)) 
          for k in range(len(C))
          if i+j+k <= N
         ]
  
result = sorted(result)[::-1]
[print(result[i]) for i in range(N)]

### FIXED CODE ###

N = list(map(int, input().split()))[-1]
A = sorted(list(map(int, input().split())), reverse=True)[:N]
B = sorted(list(map(int, input().split())), reverse=True)[:N]
C = sorted(list(map(int, input().split())), reverse=True)[:N]

first = [i+j for i in A for j in B]
first = sorted(first, reverse=True)[:N]
second = [i+j for i in first for j in C]
result = sorted(second, reverse=True)[:N]

[print(i) for i in result]
### BUGGY CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

if a[0] > 0:
    print(-1)
    exit()

for i in range(1, n):
    if a[i] > i:
        print(-1)
        exit()
    if a[i] > a[i-1] + 1:
        print(-1)
        exit()

result = 0
last = n
b = [0 for i in range(n)]
while 1:
    for i in range(last):
        j = last - i - 1
        if a[j] != b[j]:
            start = j
            last = j
            max_diff = a[j]
            break
    if j == 0:
        print(result)
        exit()
    for i in range(max_diff):
        b[start - i] = max_diff - i
    result += max_diff

### FIXED CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

if a[0] > 0:
    print(-1)
    exit()

for i in range(1, n):
    if a[i] > i:
        print(-1)
        exit()
    if a[i] > a[i - 1] + 1:
        print(-1)
        exit()

if n == 1:
    print(0)
    exit()

result = 0

if a[n-1] != 0:
    result += a[n-1]

for i in range(2, n):
    j = n - i
    if a[j] != 0 and a[j] != a[j + 1] - 1:
            result += a[j]

print(result)
### BUGGY CODE ###

from itertools import accumulate

class BIT:
  def __init__(self, size):
    self.bit = [0] * (size + 1)
    self.size = size

  def sum(self, i):
    i += 1
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s

  def add(self, i, x):
    i += 1
    while i <= self.size:
      self.bit[i] += x
      i += i & -i

N = int(input())
a = list(map(int, input().split()))
lb, ub = -1, 10**9
while ub - lb > 1:
  m = (lb + ub) // 2
  b = [0] * (N+1)
  for i in range(N):
    if a[i] <= m:
      b[i+1] = 1
  b = list(accumulate(b))
  bit_odd = BIT(2*N)
  bit_even = BIT(2*N)
  cnt = 0
  for i in range(N):
    x = N + b[i+1] - i//2 - 1
    y = N + b[i+1] - (i+1)//2 - 1
    if i % 2 == 0:
      bit_even.add(N + b[i] - i//2, 1)
      cnt += bit_even.sum(x) + bit_odd.sum(y)
    else:
      bit_odd.add(N + b[i] - i//2, 1)
      cnt += bit_even.sum(y) + bit_odd.sum(x)
  if cnt < N*(N+1)//4 + 1:
    lb = m
  else:
    ub = m
print(ub)

### FIXED CODE ###

from itertools import accumulate

class BIT:
  def __init__(self, size):
    self.bit = [0] * (size + 1)
    self.size = size

  def sum(self, i):
    i += 1
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s

  def add(self, i, x):
    i += 1
    while i <= self.size:
      self.bit[i] += x
      i += i & -i

N = int(input())
a = list(map(int, input().split()))
lb, ub = -1, 10**9
while ub - lb > 1:
  m = (lb + ub) // 2
  b = [0] * (N+1)
  for i in range(N):
    if a[i] <= m:
      b[i+1] = 1
  b = list(accumulate(b))
  bit_odd = BIT(2*N)
  bit_even = BIT(2*N)
  cnt = 0
  for i in range(N):
    x = N + b[i+1] - i//2 - 1
    y = N + b[i+1] - (i+1)//2 - 1
    if i % 2 == 0:
      bit_even.add(N + b[i] - i//2, 1)
      cnt += bit_even.sum(x) + bit_odd.sum(y)
    else:
      bit_odd.add(N + b[i] - i//2, 1)
      cnt += bit_even.sum(y) + bit_odd.sum(x)
  if cnt < N*(N+1)//4 + 1:
    lb = m
  else:
    ub = m
print(ub)
### BUGGY CODE ###

S = input()[::-1]
MOD = 10**9+7
dp = [0,]*13
dp[0] = 1
for i, s in enumerate(S):
    nx = [0,]*13
    p = (10**i)%13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
print(dp[5])

### FIXED CODE ###

S = input()[::-1]
MOD = 10**9+7
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]
p = 1
for i, s in enumerate(S):
    nx = [0,]*13
    if s == '?':
        for k in range(10):
            q = (k*p)%13
            for j, d in enumerate(dp):
                nx[(j+q)%13] += d
    else:
        q = (int(s)*p)%13
        for j, d in enumerate(dp):
            nx[(j+q)%13] += d
    dp = [n % MOD for n in nx]
    p = (10*p)%13
print(dp[5])
### BUGGY CODE ###

N , M = map(int, input().split())

L=[[0]*2 for i in range(M)]

for i in range(M):
    L[i][0] , L[i][1] = map(int, input().split())

A=[10**10]*M
B=[10**9]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break

for i in A:
    if i == 10**10 : 
        print("IMPOSSIBLE")
        exit()
    if i in B:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


### FIXED CODE ###

N , M = map(int, input().split())

L=[[0]*2 for i in range(M)]

for i in range(M):
    L[i][0] , L[i][1] = map(int, input().split())

A=[0]*M
B=[0]*M

L=sorted(L ,key=lambda x: x[0])

for i in range(M):
    if L[i][0] == 1:
        A[i]=L[i][1]
    else:
        break
A=A[0:i]

L=sorted(L ,key=lambda x: -x[1])

for i in range(M):
    if L[i][1] == N:
        B[i]=L[i][0]
    else:
        break
B=B[0:i]

if((len(A)==0)or(len(B)==0)):
    print("IMPOSSIBLE")
    exit()
if((max(A)<min(B))or(max(B)<min(A))):
    print("IMPOSSIBLE")
    exit()

A.sort()
B.sort()
i=0
j=0
while((i<len(A))and(j<len(B))):
    if A[i] == B[j]:
        print("POSSIBLE")
        exit()
    elif A[i] > B[j]:j+=1
    else:i+=1
print("IMPOSSIBLE")