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

read = input
# read = Read(False, """
# 1 1 3
# 1
# 10000000000
# 2
# 9999999999
# 5000000000
# """).read
A,B,Q = list(map(int, read().split(' ')))
arrA = list(map(int, [read() for i in range(A)]))
arrB = list(map(int, [read() for i in range(B)]))
arrQ = list(map(int, [read() for i in range(Q)]))
arrA.sort()
arrB.sort()
import bisect
def cs(x, arr):
    al = bisect.bisect_left(arr, x)
    return list(map(lambda i: arr[i], filter(lambda i:i>=0 and i< len(arr), range(al-1, al + 2))))
def same_s(da,db):
    da = da / abs(da)
    db = db / abs(db)
    return da*db>0
    
def t(q,a,b):
    da = q - a
    db = q - b
    if(min(abs(da), abs(db)) == 0):
        return max(abs(da), abs(db))
    if same_s(da, db):
        return max(abs(da), abs(db))
    else :
        return 2*min(abs(da), abs(db)) + max(abs(da), abs(db))
for q in arrQ:
    optA = cs(q, arrA)
    optB = cs(q, arrB)
    ret = 10 ** 11
    for a in optA:
        for b in optB:
            ret = min(ret, t(q, a,b))
    print(ret)

### FIXED CODE ###

import bisect
read = input
bisect_right = bisect.bisect_right
# @ see https://docs.python.org/zh-cn/3/library/bisect.html
a ,b , q = map(int, read().split())
INF = 10**18
A =[-INF] + [int(read()) for i in range(a)] +[INF]
B =[-INF] + [int(read()) for i in range(b)] +[INF]
A.sort()
B.sort()
try:
    for i in range(q):
        x = int(read())
        sa = bisect_right(A, x)
        sb = bisect_right(B, x)
        ans = INF
        for pa in [A[sa - 1 ], A[sa]]:
            for pb in [B[sb - 1 ], B[sb]]:
                d1 = abs(x - pa) + abs(pa - pb)
                d2 = abs(x - pb) + abs(pb - pa)
                ans = min(ans, d1, d2)
        print(ans)
except:
    print(x, sa, sb)
### BUGGY CODE ###

import bisect
N,Q=map(int,input().split())
STX=[list(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])


### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

rl = sys.stdin.buffer.readline
INF = sys.maxsize

X = int(rl())
SS = [c for c in rl().strip()]

W = ord(b'W')
R = ord(b'R')

last_pos = len(SS)-1
swap_count = 0
for i in range(len(SS)):
  if SS[i] == W:
    for j in range(last_pos, i, -1):
      if SS[j] == R:
        tmp = SS[i]
        SS[i] = SS[j]
        SS[j] = tmp
        last_pos = j-1
        swap_count += 1
        break

print(swap_count)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

rl = sys.stdin.buffer.readline
INF = sys.maxsize

X = int(rl())
SS = [c for c in rl().strip()]

W = ord(b'W')
R = ord(b'R')

WP = []
RP = []
for i in range(len(SS)):
  if SS[i] == W:
    WP.append(i)
  elif SS[i] == R:
    RP.append(i)

RP.reverse()

WP = deque(WP)
RP = deque(RP)

sc = 0
while len(WP) != 0 and len(RP) != 0:
  w = WP.popleft()
  r = RP.popleft()
  if w < r:
    sc += 1

print(sc)
### BUGGY CODE ###

import itertools

H, W = [int(_) for _ in input().split()]
A = [[_ for _ in input()] for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == '#':
        A[i][j] = 0
        break
stack = [[i, j]]
while stack:
    i, j = stack.pop()
    for ni, nj in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < H and 0 <= nj < W:
            if A[ni][nj] == '#':
                A[ni][nj] = 0
                stack += [[ni, nj]]
            elif A[ni][nj] == '.' or A[i][j] + 1 < A[ni][nj]:
                A[ni][nj] = A[i][j] + 1
                stack += [[ni, nj]]
print(max(max(_) for _ in A))


### FIXED CODE ###

import itertools
from collections import deque

H, W = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
Q = deque([])
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == '#':
        Q += [[i, j, 0]]
while Q:
    i, j, d = Q.popleft()
    for ni, nj in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == '.':
            A[ni][nj] = '#'
            Q += [[ni, nj, d + 1]]
print(d)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq as hq
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(lambda x: int(x) - 1, input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ans
    for t in rg[s]:
        return dfs(t)
    else:
        ans[s] = 0
        return s


def bfs(s, dep):
    global ans
    global dist
    h = [[-dep, s]]
    while h:
        d, u = hq.heappop(h)
        if dist[u] > -d:
            continue
        for v in g[u]:
            if dist[v] <= dist[u] + 1:
                ans[v] = u + 1
                dist[v] = dist[u] + 1
                hq.heappush(h, [-(-d + 1), v])


ans = [None] * N
dist = [0] * N
s = dfs(0)
bfs(s, 0)

for x in ans:
    print(x)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
g = [[] for _ in range(N)]
rg = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = (int(x) - 1 for x in input().split())
    g[A].append(B)
    rg[B].append(A)


def dfs(s):
    global ts
    global used
    used[s] = True
    for t in g[s]:
        if not used[t]:
            dfs(t)
    ts.append(s)


def tsort():
    global ts
    for i in range(N):
        dfs(i)
    ts = ts[::-1]


used = [False] * N
ts = []
tsort()

mp = [None] * N
for i, x in enumerate(ts):
    mp[x] = i

ans = [0] * N
for t in ts[1:]:
    if rg[t]:
        ans[t] = ts[max(mp[s] for s in rg[t])] + 1

for x in ans:
    print(x)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Shw = ["" for _ in range(H)]
for i in range(H):
  Shw[i] = input()

d.appendleft((Ch-1, Cw-1))
score = dict()
score[(Ch-1, Cw-1)] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if (y+dy, x+dx) not in score or (score[(y+dy, x+dx)] and score[(y+dy, x+dx)] > score[(y, x)]):
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if (y+dy, x+dx) not in score or ((y+dy, x+dx) in score and score[(y+dy, x+dx)] > score[(y, x)]+1):
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx))
          score[(y+dy, x+dx)] = score[(y, x)]+1

if (Dh-1, Dw-1) in score:
  print(score[(Dh-1, Dw-1)])
else:
  print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
d = deque() # 初期化

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Shw = [input() for _ in range(H)]

d.appendleft((Ch-1, Cw-1, 0))
score = [[-1] * W for _ in range(H)]
score[Ch-1][Cw-1] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x, s = d.popleft()
  
  # walk
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx, s))
          score[y+dy][x+dx] = s
          
  # warp
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx, s+1))
          score[y+dy][x+dx] = s+1

print(score[Dh-1][Dw-1])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
pow2 = [2 ** i for i in range(61)]
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    for k in range(60):
        if pow2[k] - a[i] != a[i]:
            if d[pow2[k] - a[i]] > 0 and d[a[i]] > 0:
                num += 1
                d[pow2[k] - a[i]] -= 1
                d[a[i]] -= 1
                break
        else:
            if d[a[i]] >= 2:
                num += 1
                d[a[i]] -= 2
                break
print(num)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
pow2 = [1]
for i in range(31):
    pow2.append(pow2[-1] * 2)
a = sorted(a, reverse=True)
d = defaultdict(int)
for i in a:
    d[i] += 1


num = 0
for i in range(N):
    if d[a[i]] == 0:
        continue
    for k in range(30, -1, -1):
        inv = pow2[k] - a[i]
        if inv < 0 or inv > a[i]:
            continue
        if inv != a[i]:
            if d[inv] > 0 and d[a[i]] > 0:
                p = min(d[inv], d[a[i]])
                num += p
                d[inv] -= p
                d[a[i]] -= p
                break
        else:
            if d[a[i]] >= 2:
                num += d[a[i]] // 2
                d[a[i]] %= 2
                break
print(num)
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]
ab = []

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
for d in ab:
    if d[1] == N:
        c.append(d[0])

for d in ab:
    if d[1] in c and d[0] == 1:
        possible = True

if possible:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
ab = []

possible = False
for _ in range(M):
    ab.append([int(i) for i in input().split()])
    

c = []
e = []
for d in ab:
    if d[1] == N:
        c.append(d[0])
    elif d[0] == 1:
        e.append(d[1])

if len(set(c) & set(e)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import defaultdict
from operator import mul
from functools import reduce


memo = {}


def cmb(n, r):
    if (n, r) in memo:
        return memo[(n, r)]
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    memo[(n, r)] = over // under
    return over // under


s = input()[::-1]
acc = [int(s[0])]
cntr = defaultdict(int)
for i, c in enumerate(s[1:], 1):
    if c == '0':
        continue
    next_mod = (acc[-1] + 10 ** i * int(c)) % 2019
    cntr[next_mod] += 1
    acc.append(next_mod)

ans = 0
for k, v in cntr.items():
    if k == 0:
        ans += v
    if v > 1:
        ans += cmb(v, 2)
print(ans)


### FIXED CODE ###

from collections import defaultdict


s = input()[::-1]
cntr = defaultdict(int)
cntr[0] += 1
tens = 1
n = 0
for c in s:
    n += tens * int(c) % 2019
    n %= 2019
    cntr[n] += 1
    tens = tens * 10 % 2019

ans = 0
for v in cntr.values():
    if v > 1:
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
A=[*map(int,input().split())]
# print(n,k)
# print(A)
B = []
for i in range(min(20,k)):
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        x = j + 1
        l = max(1, abs(x-d)) # 範囲
        r = min(n, abs(x+d)) # 範囲
        # print('x,l,r',x,l,r)
        for k in range(l-1,r): # (l,r)
            B[k] += 1
        # print('---')
    # print(B)
    A = B

print(*A, sep=' ')


### FIXED CODE ###

n,k = map(int,input().split())
A=[*map(int,input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = j+d+1 # 範囲
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    # print(B)
    if is_same: break
    A = B
# print(B)
print(*B,sep=' ')
### BUGGY CODE ###


import math


def fact(x):
    for cand in range(2, math.ceil(math.sqrt(x)) + 1):
        q, r = divmod(x, cand)
        if r == 0:
            return min(q, cand), max(q, cand)
    return 1, x


# def check(a, b):
#     a2 = a * a
#     a3 = a2 * a
#     a4 = a3 * a
#     b2 = b * b
#     b3 = b2 * b
#     b4 = b3 * b
#     return a4 + a3*b + a2*b2 + a*b3 + b4

def pow5(x):
    return x ** 5


def func(a, b):
    return pow5(a) - pow5(b)


def submit():
    x = int(input())

    if x == 1:
        print("0 -1")
        return

    q1, q2 = fact(x)

    # パターン1, a, b > 0
    a = q1
    b = 0
    f = func(a, b)
    while f < x:
        a += 1
        b += 1
        f = func(a, b)
    if f == x:
        print("{} {}".format(a, b))
        return

    # パターン2 a > 0, b < 0
    a = q1 - 1
    b = -1
    f = func(a, b)
    while a > 0 and f != x:
        a -= 1
        b -= 1
        f = func(a, b)
    if f == x:
        print("{} {}".format(a, b))
        return

    # パターン3 a, b < 0
    a = 0
    b = -q1
    f = func(a, b)
    while f != x:
        a -= 1
        b -= 1
        f = func(a, b)
    if f == x:
        print("{} {}".format(a, b))
        return

        
submit()

### FIXED CODE ###



def submit():
    x = int(input())

    for a in range(-200, 200):
        for b in range(-200, 200):
            if a ** 5 - b ** 5 == x:
                print(a, b)
                return


if __name__ == "__main__":
    submit()
### BUGGY CODE ###

n,m = map(int,input().split())
job = [(0,0) for _ in range(n)]
salary = [0 for _ in range(n)]

for i in range(n):
    a,b= map(int,input().split())
    job[i] = a,b
    salary[i] = b
job.sort(reverse = True)
max = max(salary)
salary = [max+1 for _ in range(n)]

for j in range(n):
    s,t = job[j]
    salary[j] = t

    if s - m > 0:
        salary[salary.index(min(salary))] = max+1
    else:
        m -= 1
for k in range(n):
    if salary[k] == max+1:
        salary[k] = 0
print(sum(salary))


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))
### BUGGY CODE ###

import collections
N = int(input())
D = [int(i) for i in input().split()]+[0, 24]

C = collections.Counter(D)
if C.most_common()[0][1] >= 3:
    print(0)
    exit()

ans = 0
for i in range(2 ** N):
    D0 = D
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            D0[j] = 24-D0[j]
        D0 = sorted(D0)
        c = 24
        for k in range(N+1):
            c = min(c, D0[k+1]-D0[k])
    ans = max(ans, c)

print(ans)


### FIXED CODE ###

import collections
import copy
N = int(input())
D = [int(i) for i in input().split()]

C = collections.Counter(D)
if C.most_common()[0][1] >= 3:
    print(0)
    exit()

D1 = [0, 24]
m = []
for k, v in C.items():
    if v == 2:
        D1.append(k)
        D1.append(24-k)
    elif v == 1:
        m.append(k)

ans = 0
for i in range(2 ** len(m)):
    D0 = copy.deepcopy(D1)
    for j in range(len(m)):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            D0.append(24-m[j])
        else:
            D0.append(m[j])

    # print(D0)

    D0 = sorted(D0)
    c = 24
    for i in range(N+1):
        c = min(c, D0[i+1]-D0[i])
    ans = max(ans, c)

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

def main():
    n = int(input())
    l_dic = {}
    r_dic = {}
    i = 0
    for a in map(int, input().split()):
        ld = l_dic.setdefault(i + a, [])
        ld.append(i)
        rd = r_dic.setdefault(i-a, [])
        rd.append(i)
        i += 1

    count = 0
    for rk, rv_list in r_dic.items():
        if rk not in l_dic:
            continue
        lv_list = l_dic[rk]
        for rv in rv_list:
            # count += len([lv for lv in lv_list if lv < rv])
            for lv in lv_list:
                if lv < rv:
                    count += 1
                else:
                    break

    print(count)


main()



### FIXED CODE ###

def is_ok(mid: int, target: int, ls: []):
    return target <= ls[mid]


def bi_search(target: int, ls: []):
    ng = -1
    ok = len(ls)

    cnt = 0
    while ok - ng > 1:
        mid = ng + int((ok - ng) / 2)
        cnt += 1
        if is_ok(mid, target, ls):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    n = int(input())
    l_dic = {}
    r_dic = {}
    i = 0
    for a in map(int, input().split()):
        ld = l_dic.setdefault(i + a, [])
        ld.append(i)
        rd = r_dic.setdefault(i - a, [])
        rd.append(i)
        i += 1

    count = 0
    for rk, rv_list in r_dic.items():
        if rk not in l_dic:
            continue
        lv_list = l_dic[rk]
        for rv in rv_list:
            ind = bi_search(rv, lv_list)
            if ind == len(lv_list):
                count += ind
            else:
                count += ind + 1
            # for lv in lv_list:
            #     if lv < rv:
            #         count += 1
            #     else:
            #         break

    print(count)


main()
### BUGGY CODE ###

import math

s = input()
i = int(input())

for _ in range(i):
    q = input().split(" ")
    if q[0] == "1":
        s = s[::-1]
    else:
        if q[1] == "1":
            s = q[2] + s
        else:
            s = s + q[2]

print(s)

### FIXED CODE ###

import math

s = input()
i = int(input())

isR = False
head = []
tail = []

for _ in range(i):
    q = input().split(" ")

    if q[0] == "1":
        isR = not isR
    else:
        if isR:
            if q[1] == "1":
                tail.append(q[2])
            else:
                head.append(q[2])
        else:
            if q[1] == "1":
                head.append(q[2])
            else:
                tail.append(q[2])

ans = "".join(head[::-1]) + s + "".join(tail)

if isR:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

s = list(input())

n = len(s)

a = [0] * n

MOD = 998244353

for i in range(n):
    a[i] = ord(s[i]) - ord('a')

if max(a) == min(a):
    print(1)
    exit()
elif n == 3:
    def solver(m):
        x = m // 100
        y = ( m % 100 ) // 10
        z = m % 10
        if x != y:
            c = (3 - x - y) % 3
            temp = c * 110 + z
            if temp not in ans:
                ans.add(temp)
                solver(temp)
        if y != z:
            c = (3 - y - z) % 3
            temp = x * 100 + c * 11
            if temp not in ans:
                ans.add(temp)
                solver(temp)

    t = a[0] * 100 + a[1] * 10 + a[2]
    ans = set()
    ans.add(t)
    solver(t)
    print(len(ans))
    exit()
elif n == 2:
    print(2)
    exit()

dp = [[0,0,0] for _ in range(3)]

dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1

for i in range(n-1):
    T = [[0,0,0] for _ in range(3)]
    T[0][0] = dp[1][0] + dp[2][0]
    T[0][1] = dp[1][1] + dp[2][1]
    T[0][2] = dp[1][2] + dp[2][2]
    T[1][0] = dp[0][2] + dp[2][2]
    T[1][1] = dp[0][0] + dp[2][0]
    T[1][2] = dp[0][1] + dp[2][1]
    T[2][0] = dp[0][1] + dp[1][1]
    T[2][1] = dp[0][2] + dp[1][2]
    T[2][2] = dp[0][0] + dp[1][0]
    dp, T = T, dp

m = sum(a) % 3

ans = 3 ** (n-1) - (dp[0][m] + dp[1][m] + dp[2][m])

check = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        check = 0
        break

ans += check

print(ans % MOD)


### FIXED CODE ###

s = list(input())

n = len(s)

a = [0] * n

MOD = 998244353

for i in range(n):
    a[i] = ord(s[i]) - ord('a')

if max(a) == min(a):
    print(1)
    exit()
elif n == 3:
    def solver(m):
        x = m // 100
        y = ( m % 100 ) // 10
        z = m % 10
        if x != y:
            c = (3 - x - y) % 3
            temp = c * 110 + z
            if temp not in ans:
                ans.add(temp)
                solver(temp)
        if y != z:
            c = (3 - y - z) % 3
            temp = x * 100 + c * 11
            if temp not in ans:
                ans.add(temp)
                solver(temp)

    t = a[0] * 100 + a[1] * 10 + a[2]
    ans = set()
    ans.add(t)
    solver(t)
    print(len(ans))
    exit()
elif n == 2:
    print(2)
    exit()

dp = [[0,0,0] for _ in range(3)]

dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1

for i in range(n-1):
    T = [[0,0,0] for _ in range(3)]
    T[0][0] = (dp[1][0] + dp[2][0]) % MOD
    T[0][1] = (dp[1][1] + dp[2][1]) % MOD
    T[0][2] = (dp[1][2] + dp[2][2]) % MOD
    T[1][0] = (dp[0][2] + dp[2][2]) % MOD
    T[1][1] = (dp[0][0] + dp[2][0]) % MOD
    T[1][2] = (dp[0][1] + dp[2][1]) % MOD
    T[2][0] = (dp[0][1] + dp[1][1]) % MOD
    T[2][1] = (dp[0][2] + dp[1][2]) % MOD
    T[2][2] = (dp[0][0] + dp[1][0]) % MOD
    dp, T = T, dp

m = sum(a) % 3

ans = 3 ** (n-1) - (dp[0][m] + dp[1][m] + dp[2][m])

check = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        check = 0
        break

ans += check

#print(dp, 2 ** (n-1))

print(ans % MOD)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    Query = [i for i in input().split()]
    if Query[0] == '1':
        S = S[::-1]
    else:
        if Query[1] == '1':
            S = ''.join([Query[2], S])
        else:
            S = ''.join([S, Query[2]])
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
R = 1  # 1:False, -1:True
P = []
B = []
for _ in range(Q):
    Query = [i for i in input().split()]
    if Query[0] == '1':
        R *= -1
    else:
        if R == 1:
            if Query[1] == '1':
                P.append(Query[2])
            else:
                B.append(Query[2])
        else:
            if Query[1] == '1':
                B.append(Query[2][::-1])
            else:
                P.append(Query[2][::-1])

ans = ''.join(P[::-1])+S+''.join(B)
if R == -1:
    ans = ans[::-1]

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

n = int(input())
table = {}
for i in range(n):
    a = int(input())
    table[i] = a-1

is_visited = [ False for _ in range(n) ]
is_visited[0] = True

cnt = 0
now = 0
while True:
    if now == 1:
        print(cnt)
        break
    nxt = table[now]
    if is_visited[nxt]:
        print(-1)
        break
    now = nxt
    cnt += 1

### FIXED CODE ###

n = int(input())
table = {}
for i in range(n):
    a = int(input())
    table[i] = a-1

is_visited = [ False for _ in range(n) ]
is_visited[0] = True

cnt = 0
now = 0
while True:
    is_visited[now] = True
    if now == 1:
        print(cnt)
        break
    nxt = table[now]
    if is_visited[nxt]:
        print(-1)
        break
    now = nxt
    cnt += 1