Harryxun/stf_run huggingface dataset:
N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(Q)][: : -1]
res = [N * (N - 1) // 2]
mod = 2305843009213693951
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

uf = UnionFind(N)
f = Factorial(N * (N - 1) // 2, 2305843009213693951)
for b in A:
  uf.Unite(b[0], b[1])
  convenience = 0
  for inc in uf.root:
    if inc < -1:
      convenience += f.combi(-inc, 2)
  res.append(N * (N - 1) // 2 - convenience)
for i in range(Q - 1, -1, -1):
  print(res[i])

### FIXED CODE ###

N, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(Q)]
res = [0] * (Q - 1) + [N * (N - 1) // 2]
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N)
convenience = [0] * (N + 1)
for i in range(Q - 1, 0, -1):
  res[i - 1] = res[i]
  if uf.Find_Root(A[i][0]) != uf.Find_Root(A[i][1]):
    res[i - 1] -= uf.Count(A[i][0]) * uf.Count(A[i][1])
    a, b = uf.Count(A[i][0]), uf.Count(A[i][1])
    uf.Unite(A[i][0], A[i][1])
  #print(uf.root, res, a, b)
for i in range(Q):
  print(res[i])
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
wl=[]
for i in range(h):
    wf=0
    for j in range(w):
        if l[i][j]=='.':
            wf+=1
    if wf<w:
        wl.append(i)
    
hl=[]
for i in range(w):
    hf=0
    for j in range(h):
        if l[j][i]=='.':
            hf+=1
    if hf<h:
        hl.append(i)
for i in hl:
    for j in wl:
        print(l[i][j],end='')
    print()


### FIXED CODE ###

h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
wl=[]
for i in range(h):
    wf=0
    for j in range(w):
        if l[i][j]=='.':
            wf+=1
    if wf<w:
        wl.append(i)
    
hl=[]
for i in range(w):
    hf=0
    for j in range(h):
        if l[j][i]=='.':
            hf+=1
    if hf<h:
        hl.append(i)
for i in wl:
    for j in hl:
        print(l[i][j],end='')
    print()
import math

a=int(input())
#li = list(map(int,input().split()))
print(math.ceil(li[0]/a)*a)
if li[1]<math.ceil(li[0]/a)*a:
    print("NG")
else:
    print("OK")

### FIXED CODE ###

import math
 
a=int(input())
li = list(map(int,input().split()))
#print(math.ceil(li[0]/a)*a)
if li[1]<math.ceil(li[0]/a)*a:
    print("NG")
else:
    print("OK")
a,b,c=map(int,input().split())
k=int(input())
count=0
while(b<=a):
    b*=2
    count+=1
while(c<=b):
    c*=2
    count+=1
if count<=k:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

x=int(input())
if x>=400 and x<=599:
    print(8)
elif x>=600 and x<=799:
    print(7)
elif x>=800 and x<=999:
    print(6)
elif x>=1000 and x<=1199:
    print(5)
elif x>=1200 and x<=1399:
    print(4)
elif x>=1400 and x<=1599:
    print(3)
elif x>=1600 and x<=1799:
    print(2)
else:
    print(1)
def main14():
    strbuf = input('');
    num = int(strbuf);
    kari = num;
    peku = 0;
    while(True):
        iti = int(kari % 10);
        peku = iti;
        if(iti<10):
            break;
        iti = (kari - iti) / 10;
    if((int(num % peku) == 0)):
        print("Yes");
    else:
        print("No");

if __name__ == '__main__':
    main14()

### FIXED CODE ###

def main14():
    strbuf = input('');
    num = int(strbuf);
    kari = num;
    peku = 0;
    while(True):
        iti = int(kari % 10);
        peku = peku + iti;
        if(kari<10):
            break;
        kari = (kari - iti) / 10;
    if((int(num % peku) == 0)):
        print("Yes");
    else:
        print("No");

def main15():
    strbuf1 = input('');
    strbuf2 = input('');
    buf1 = [];
    buf2 = [];
    for i in range(2):
        buf1.append(int(strbuf1[i]));
    for i in range(buf1[0]):
        buf2.append(int(strbuf2[i]));


if __name__ == '__main__':
    main14()
res = A - 2 * B
if res <= 0: res = 0
print(res)

### FIXED CODE ###

A, B = map(int, input().split())
res = A - 2*B
if res < 0: res = 0
print(res)
r=int(input())
print(3*(a**2))

### FIXED CODE ###

r=int(input())
print(3*(r**2))
a,b,c=int().input.split()
count=0
for i in range(a,b+1) :
    if c%i == 0:
        count += 1
print(count)

### FIXED CODE ###

a,b,c=map(int,input().split())
d=[i for i in range(a,b+1)]
count=0
for i in d:
    if c%i==0:
        count+=1
print(count)
a=list(map(int,input().split(' ')))
print(min(a[0],a[1])+min(a[2],a[3]))

### FIXED CODE ###

a=[]
for i in range(4):
 a.append(int(input()))
print(min(a[0],a[1])+min(a[2],a[3]))
N = int(input())
R = int(input())

if(N<10):
  print(R+(100*(10-N)))
else:
  print(R)

### FIXED CODE ###

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

if(N<10):
  print(R+100*(10-N))
else:
  print(R)
using System;

class Test
{
    public static void Main()
    {
        int a;
        a=int.Parse(Console.ReadLine());
        a = 3 * a * a * a;
        Console.WriteLine(a);
    }
}

### FIXED CODE ###

r=int(input())

print(3*r*r)
strs = input().split()
if strs[0][len(strs[0]) -1] == strs[1][0] and strs[1][len(strs[0]) -1] == strs[2][0]:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

strs = input().split()
if strs[0][len(strs[0]) -1] == strs[1][0] and strs[1][len(strs[1]) -1] == strs[2][0]:
    print("YES")
else:
    print("NO")
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))
if n==2:
    print(0)
    exit()


def f(x,y,c):
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            used[e] = 1
        f(e,x,c)


if k % 2 == 0:
    d = k//2
    res = []
    for i in range(n):
        used = [0]*n
        f(i,-1,0)
        res.append(sum(used))
    print(min(res))
else:
    d = (k-1)//2
    res = []
    for e1 in alledge:
        used = [0]*n
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        res.append(sum(used))
    print(min(res))


### FIXED CODE ###

import sys
#input = sys.stdin.readline
n,k = map(int,input().split())
edge = [[] for i in range(n)]
alledge = []
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    alledge.append((a-1,b-1))

def f(x,y,c):
    global tmp
    c += 1
    for e in edge[x]:
        if e == y:
            continue
        if c > d:
            tmp +=1
        f(e,x,c)

sys.setrecursionlimit(4100000)

if k % 2 == 0:
    d = k//2
    ass = 2001
    for i in range(n):
        tmp = 0
        f(i,-1,0)
        ass = min(ass,tmp)
    print(ass)
else:
    d = (k-1)//2
    ass = 2001
    for e1 in alledge:
        tmp = 0
        f(e1[0],e1[1],0)
        f(e1[1],e1[0],0)
        ass = min(ass,tmp)
    print(ass)
n = int(input())
m = int(input())
print((n-1)*(m-1))

### FIXED CODE ###

n,m = map(int, input().split())
print((n-1)*(m-1))
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

L = []
R = []

for i in range(H):
  R_cnt = 0
  for j in range(W):
    if A[i][j] == '.':
      R_cnt += 1
  if R_cnt == W:
    R.append(i)

for j in range(W):
  L_cnt = 0
  for i in range(H):
    if A[i][j] == '.':
      L_cnt += 1
  if L_cnt == H:
    L.append(j)

for i in range(H):
  S = []
  for j in range(W):
    if i in R or j in L:
      break
    else:
      S.append(A[i][j])
  print(' '.join(S))

### FIXED CODE ###

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

L = []
R = []

for i in range(H):
  R_cnt = 0
  for j in range(W):
    if A[i][j] == '.':
      R_cnt += 1
  if R_cnt == W:
    R.append(i)

for j in range(W):
  L_cnt = 0
  for i in range(H):
    if A[i][j] == '.':
      L_cnt += 1
  if L_cnt == H:
    L.append(j)

for i in range(H):
  S = []
  for j in range(W):
    if i in R:
      break
    elif j in L:
      continue
    else:
      S.append(A[i][j])
  if len(S) > 0:
    print(''.join(S))
k = int(input())
a = list(map(int, input().split()))

can = []
res = []

def solve():

    for i in range(k):
        a_ = a[k-i-1]

        if i==0:
            res = [2]
        else:
            res = []
            for c in can:
                if c % a_ == 0:
                    res.append(c)
            if len(res) == 0:
                print(-1)
                return

        can = []
        for r in res:
            can = can + list(range(r, r+a[k-i-1]))

        #print(i, res, a_, can)
    print(min(can), max(can))
solve()


### FIXED CODE ###

k = int(input())
a = list(map(int, input().split()))
def solve():

    if a[k-1] != 2:
        print(-1)
        return

    mi = 2
    mx = 2

    for i in range(k):
        j = k-i-1

        mx = mx + a[j] - 1

        if j == 0:
            pass
        else:
            na = a[j-1]
            
            if mx % na != 0 and mi % na != 0 and ((mx % na) - (mi % na)) == (mx - mi):
                print(-1)
                return

            if mi%na != 0:
                mi = mi + (na - mi%na)

            if mx%na != 0:
                mx = mx - (mx % na)

    print(mi, mx)
solve()
import numpy as np

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = np.zeros((len_s + 1, len_t + 1), dtype=np.int)
for index_s in range(len_s):
  char_s = s[index_s]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp[index_s + 1, index_t + 1] = dp[index_s, index_t] + 1
    else:
      dp[index_s + 1, index_t + 1] = max(
        dp[index_s, index_t + 1], dp[index_s + 1, index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp[-1, -1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s, index_t + 1] == len_lcs:
    index_s -= 1
  elif dp[index_s + 1, index_t] == len_lcs:
    index_t -= 1
  else:
    raise ValueError
print(''.join(lcs_reverse[::-1]))

### FIXED CODE ###

s = input()
t = input()
len_s, len_t = len(s), len(t)
dp = [[0] * (len_t + 1) for _ in range(len_s + 1)]
for index_s in range(len_s):
  char_s = s[index_s]
  dp_s = dp[index_s]
  dp_ss = dp[index_s + 1]
  for index_t in range(len_t):
    if char_s == t[index_t]:
      dp_ss[index_t + 1] = dp_s[index_t] + 1
    else:
      dp_ss[index_t + 1] = max(dp_s[index_t + 1], dp_ss[index_t])
index_s, index_t = len_s - 1, len_t - 1
lcs_reverse = []
len_lcs = dp_ss[-1]
while len_lcs > 0:
  if s[index_s] == t[index_t]:
    lcs_reverse.append(s[index_s])
    index_s -= 1
    index_t -= 1
    len_lcs -= 1
  elif dp[index_s][index_t + 1] == len_lcs:
    index_s -= 1
  else:
    index_t -= 1
print(''.join(lcs_reverse[::-1]))
S = input()
T = input()

ans = 0
for i in len(S):
  if S[i] == T[i]:
    ans += 1
    
print(ans)

### FIXED CODE ###

S = input()
T = input()

ans = 0
for i in range(len(S)):
  if S[i] == T[i]:
    ans += 1
    
print(ans)
import sys
input = sys.stdin.readline

import numpy as np

def main():
    #1:初期化
    N,W = map(int,input().split())
    wv = []
    for _ in range(N):
        wv.append(list(map(int,input().split())))
    dp = np.zeros((W+1,N+1), dtype=int)
    #dp = [[0]*(W+1) for i in range(N+1)]

    #print(wv)
    #print(dp)
    #2:初期値(元からゼロなので記述無し)

    #3:dp実行部(貰うDP)
    for i in range(1,N+1):
        for j in range(1,W+1):
            if wv[i-1][0] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
            #print(i,j)
            #print(*dp,sep="\n")

    #4:出力
    print(dp[N][W])

if __name__ == '__main__':
    main()

### FIXED CODE ###

#1:初期化
N = int(input())
h = list(map(int, input().split()))
inf = float("inf")
dp = [inf]*(N)

#2:初期値
dp[0] = 0

#3:dp実行部
for i in range(1,N):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if(i>1): #2つ目の足場には二個前の足場がないので．
        dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

#4:出力
print(dp[N-1])
K, X = map(int, input().split())

l = K // 2
lower = X - l
upper = X + l
ans = [i for i in range(lower, upper+1)]
ans_str = " ".join(ans)
print(ans_str)

### FIXED CODE ###

K, X = map(int, input().split())

lower = X - K + 1
upper = X + K - 1
ans = [i for i in range(lower, upper+1)]
ans_str = " ".join(list(map(str, ans)))
print(ans_str)
n,m=map(int,input().split())
ab = []
for _ in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    #print(v)
    cnt += 1
  
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
ab = []
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ab.append({a,b})
import itertools

cnt = 0
for v in itertools.permutations(range(1,n)):
  l = 0
  ok = True
  for v2 in v:
    if {l,v2} not in ab:
      ok = False
      break
    l = v2
  if ok:
    #print(v)
    cnt += 1
  
print(cnt)
N=int(input())
A=[int(i) for i in input().split()]

count=0
for i in A:
	if i%2==1:
		count+=1
if count%2==0:
	print("YES")
else:
	print("NO)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]

count=0
for i in A:
	if i%2==1:
		count+=1
if count%2==0:
	print("YES")
else:
	print("NO")
n,k = map(int,input().split())
a = list(map(int,input().split()))
pos = 0
visit = [0] * n
move = []
loop = []
while visit[pos] != 2:
    if visit[pos] == 0:
        move.append(pos)
    else:
        loop.append(pos)
    visit[pos] += 1
    pos = a[pos] - 1
if len(move[k]) > k:
    print(move[k]+1)
else:
    print(loop[(k-(len(move)-len(loop)))%len(loop)]+1)


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
pos = 0
visit = [0] * n
move = []
loop = []
while visit[pos] != 2:
    if visit[pos] == 0:
        move.append(pos)
    else:
        loop.append(pos)
    visit[pos] += 1
    pos = a[pos] - 1
if len(move) > k:
    print(move[k]+1)
else:
    print(loop[(k-(len(move)-len(loop)))%len(loop)]+1)
# coding: utf-8

import math

N = int(raw_input())

h = int(math.ceil(N/4.0))
n = int(math.ceil(h*4*N/4.0/(h*4-N)))
w = int(math.ceil(N*n*h-4*n-4*h))
print h, n, w

### FIXED CODE ###

def solver():
    N = int(raw_input())

    for h in xrange(1, 3501):
        for n in xrange(1, 3501):
            x = N * h * n;
            y = 4 * n * h - N * n - N * h;
            if y > 0 and x % y == 0:
                w = x / y
                return map(str, [h, n, w])


print " ".join(solver())
# -*- coding: utf-8 -*-
n=int(input())
numlista=map(int,input().split())
#aの合計を求める
suma=0
for i in range(n):
  suma+=numlista[i]
#
#q=int(input())
#for i in range(q):
#  b,c=int(input().split())
#  k=c-b
print(numlista)
print(suma)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n=int(input())
numlista=list(map(int,input().split()))
import collections
numkosuu=collections.Counter(numlista)
suma=0
for i in numlista:
  suma+=i
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
#変化したところのみ計算する
  suma+=(c-b)*numkosuu[b]
#個数を更新する
  numkosuu[c]+=numkosuu[b]
  numkosuu[b]=0
  print(suma)
N=int(input())
IDs =list(map(int,input().split()))

for i in range(1,N+1):
    print(IDs.count(i))

### FIXED CODE ###

R=int(input())

import math

print(math.pi*R*2)
n=int(input())
list=[int(input()) for x in range(n)]
a=0
for j in range(n):
  if max(list[:j])<=list[j]:
    a=a+1
  else:
    pass
print(a)

### FIXED CODE ###

n=int(input())
list=list(map(int,input().split()))
a=1
for j in range(n-1):
  if max(list[:j+1])<=list[j+1]:
    a=a+1
  else:
    pass
print(a)
N = input()
num = 1
while True:
  if num**2 > N:
    print((num-1)**2)
    break
  else:
    num += 1

### FIXED CODE ###

N = int(input())
num = 1
while True:
  if num**2 > N:
    print((num-1)**2)
    break
  else:
    num += 1
n=int(input())
import math
ans=[]
ans_i=[]
for i in range(1,int(math.sqrt(n))):
    if n%i==0:
        ans.append(i)
        ans_i.append(n//i)
v=list(str(max(max(ans,ans_i))))
print(len(v))

### FIXED CODE ###

import math
n=int(input())
ans=[]
for i in range(1,int(math.sqrt(n))+1):
    if n%i==0:
        ans.append(n//i)
v=min(ans)
data=int(math.log10(v)+1)
print(data)
m, t, s = input().split()
if m // s <= t:
  print('YES')
else:
  print('No')

### FIXED CODE ###

m, t, s = input().split()
if float(m) / float(s) <= float(t):
  print('Yes')
else:
  print('No')
S=input()
 
T=input()
 
if S==T-(T-S):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

S=list(input())
 
T=list(input())
Judge = True 
 
for i in range(len(S)):
  if S[i]==T[i]:
    continue
  else:
    Judge = False

if Judge:
  print("Yes")
else:
  print("No")
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

time = 0
cnt = 0
b = []

for i in B:
    if i+time>K:
        break
    time += i
    cnt += 1
    b.append(i)

b.reverse()
# print(b)
# print(cnt)
bi = 0
for i in range(N):
    if time+A[i] <= K:
        cnt += 1
        time += A[i]
    else:
        if len(b)-1 >= bi:
            if A[i] <= b[bi]:
                time -= b[bi]-A[i]
                bi += 1
        else:
            break
            # print("a")
            # print(time+A[i])
       
    # print(time)

time2 = 0
cnt2 = 0
a = []

for i in A:
    if i+time>K:
        break
    time2 += i
    cnt2 += 1
    a.append(i)

a.reverse()
# print(b)
# print(cnt)
ai = 0
for i in range(N):
    if time2+B[i] <= K:
        cnt2 += 1
        time2 += B[i]
    else:
        if len(a)-1 >= ai:
            if B[i] <= a[ai]:
                time2 -= a[ai]-B[i]
                ai += 1
        else:
            break
            # print("a")
            # print(time+A[i])
       
    # print(time)


print(max(cnt, cnt2))


### FIXED CODE ###

from itertools import accumulate

N, M, K = map(int, input().split())
A = list(accumulate([0] + list(map(int, input().split()))))
B = list(accumulate([0] + list(map(int, input().split()))))


ans, j = 0, M

for i in range(N+1):
    if A[i] > K:
        break
    while B[j] > K-A[i]:
        j -= 1
    ans = max(ans, i+j)


print(ans)
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
mod = 10**9 + 7

# n = int(input())
# a = list(map(int, input().split()))
n = int(input())
s = input()
ans = []
for i in range(s):
    ans.append(chr((ord(i)-ord('A')+n)%26 + ord('A')))

print(''.join(ans))

### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

# n = int(input())
# a = list(map(int, input().split()))
n = int(input())
s = input()
ans = []
for i in s:
    ans.append(chr((ord(i)-ord('A')+n)%26 + ord('A')))

print(''.join(ans))
from collections import defaultdict,deque
import math
import copy
def main():
    x,k,d=map(int, input().split())
    res = float('inf')
    l = 0
    r = k+1
    tmp_res = 0
    while(l+1!=r):
        mid = (l+r)//2
        tmp_res = copy.deepcopy(res)
        if((k-mid)%2==1):
         	res = min(res, abs(abs(x)-(mid+1)*d))
            res = min(res, abs(abs(x)-(mid-1)*d))
            mid+=1
        if((k-mid)%2==0):
            res = min(res, abs(abs(x)-mid*d))
            res = abs(res)
        if(abs(abs(x)-mid*d) > x):
            r = mid
        else:
            l = mid
        if tmp_res == res:
            break

    print(res)




if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict,deque
import math
import copy
def main():
    x,k,d=map(int, input().split())
    res = float('inf')
    x = abs(x)

    if(k*d <= x):
        print(x-k*d)
    else:
        if(k%2 == x//d%2):
            print(x%d)
        else:
            print(d-x%d)




if __name__ == '__main__':
    main()
s,w=map(int, input().split())
if w>=s:
  print('unsafe')
else:
  print('safe')


### FIXED CODE ###

a,b,c,d=map(int, input().split())
while a>0 or c>0:
  c-=b
  a-=d
  if c<=0:
    print('Yes')
    exit()
  elif a<=0:
    print('No')
    exit()
b = int(input())
if b == "A":
  print("T")
elif b == "C":
  print("G")
elif b == "G":
  print("C")
else:
  print("A")

### FIXED CODE ###

b = input()
if b == "A":
  print("T")
elif b == "C":
  print("G")
elif b == "G":
  print("C")
else:
  print("A")
import bisect
x, n = map(int, input().split())
pN = list(map(int, input().split()))
flag = 1
pN.sort()
key_index = bisect.bisect(pN, x) - 1
if n == 0:
    print(x)
else:
    while(1):
        if pN[key_index] - 1 != pN[key_index-1]:
            print(pN[key_index] - 1)
            break
        if flag == 1:
            if pN[key_index] + 1 != pN[key_index+1]:
                print(pN[key_index] + 1)
                break
        key_index = key_index + 1
        if(key_index >= n):
            flag = 0

### FIXED CODE ###

import bisect
x, n = map(int, input().split())
pN = list(map(int, input().split()))

pN.sort()

diff = 0

if n == 0:
    print(x)
else:
    while(1):
        if x-diff not in pN:
            print(x-diff)
            exit()
        elif x+diff not in pN:
            print(x+diff)
            exit()
        diff+=1
from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
for i in range(n):
    B.append(A[B[i]])
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None
while k < 10 ** 6:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s:
    k_max = K % (k_s - k_f)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)   

### FIXED CODE ###

from collections import Counter
N, K = map(int,input().split())
A = list(map(int,input().split()))
i = k = 0
B = [1]
while k <= 10 ** 6:
    i = A[i] - 1
    B.append(i + 1)
    k += 1
S = Counter(B)
idx = S.most_common(1)[0][0]
i = k = cnt = 0
k_s = None
while k < 10 ** 6:
    if B[k] == idx and cnt == 1:
        k_s = k
        break
    elif B[k] == idx:
        k_f = k
        cnt += 1
    k += 1
if k_s and k_s < K:
    k_max = (K - B.index(idx)) % (k_s - k_f) + B.index(idx)
else:
    k_max = K
i = k = 0
while k < k_max:
    i = A[i] - 1
    k += 1
print(i + 1)