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

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

X = abs(X)
now = X
over_zero_step = 0
over_zero = 0
not_over_zero = now
flg = 0
for i in range(1, K+1):
    if X < abs(K * D):
        nxt = now - D
    #    print(nxt, i)
        if nxt < 0:
            over_zero = nxt
            not_over_zero = now
            over_zero_step = i
            break
        now = nxt
    else:
        remaining_step = 0
        nearest_point = X - K * D
        flg = 1

if flg == 0:
        
    if abs(over_zero) <= not_over_zero:
        nearest_point = over_zero
        nearest_point_step = over_zero_step
        next_nearest_point = not_over_zero
        remaining_step = K - nearest_point_step
    else:
        nearest_point = not_over_zero
        nearest_point_step = over_zero_step - 1
        next_nearest_point = over_zero
        remaining_step = K - nearest_point_step

#print("rem", remaining_step)
if remaining_step % 2 == 0:
    print(abs(nearest_point))
else:
    print(abs(next_nearest_point))

### FIXED CODE ###

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

X = abs(X)
now = X
over_zero_step = 0
over_zero = 0
not_over_zero = now
flg = 0

if X < abs(K * D):
    q = X // D
    now = X - q * D
    now = abs(now)
#    print(now, q)    
    for i in range(q+1, K+1):
        nxt = now - D
        if nxt < 0:
            over_zero = nxt
            not_over_zero = now
            over_zero_step = i
            break
        now = nxt
else:
    remaining_step = 0
    nearest_point = X - K * D
    flg = 1

if flg == 0:
        
    if abs(over_zero) <= not_over_zero:
        nearest_point = over_zero
        nearest_point_step = over_zero_step
        next_nearest_point = not_over_zero
        remaining_step = K - nearest_point_step
    else:
        nearest_point = not_over_zero
        nearest_point_step = over_zero_step - 1
        next_nearest_point = over_zero
        remaining_step = K - nearest_point_step

#print("rem", remaining_step)
if remaining_step % 2 == 0:
    print(abs(nearest_point))
else:
    print(abs(next_nearest_point))
### BUGGY CODE ###

n = int(input())
lis = list(map(int,input().split()))
num = 0
for i in range(n):
  while lis[i] % 2 == 0:
    num += 1
    lis[i] // 2
print(num)

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
num = 0
for nu in lis:
  while nu % 2 == 0:
    num += 1
    nu = nu // 2
print(num)
### BUGGY CODE ###

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]

print(dp[-1][5] % MOD2)


### FIXED CODE ###

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
                dp[i + 1][tmp_j] %= MOD2
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]
            dp[i + 1][tmp_j] %= MOD2

print(dp[-1][5] % MOD2)
### BUGGY CODE ###

import itertools
n,a=map(int,input().split())
x=list(map(int,input().split()))
pd=list(itertools.product(range(2),repeat=n))
pd=pd[1:]
ans=0
for l in pd:
    c=0
    s=0
    for i in range(n):
        if l[i]==1:
            c+=1
            s+=x[i]
    if s/c==a:
        ans+=1
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(n*50+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(j*50+1):
            if k<x[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            else:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
ans=0
for i in range(1,n+1):
    ans+=dp[-1][i][i*a]
print(ans)
### BUGGY CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [0 for j in range(S + 1)]
dp[0] = 1
for i in range(N) : 
    for j in range(S, -1, -1) : 
        if j + A[i] <= S : 
            dp[j + A[i]] += dp[j]
            dp[j + A[i]] %= mod
        dp[j] *= 2
        dp[j] %= mod 
        
print(dp[S])

### FIXED CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [0 for j in range(S + 1)]
dp[0] = 1
for i in range(N) : 
    for j in range(S, -1, -1) : 
        if j + A[i] <= S : 
            dp[j + A[i]] += dp[j]
            dp[j + A[i]] %= mod
        dp[j] *= 2
        dp[j] %= mod 
        
print(dp[S])
### BUGGY CODE ###

n=int(input())
a=[0]*n
total=1
a=([int(x) for x in input().split()])
for i in range(n):
    total=total*a[i]
    
if total<=10**18:
    print(total)
else:
    print("-1")
                                                                  


### FIXED CODE ###

#b問題
n=int(input())
ans=1
a=list(int(y) for y in input().split())
# print(a)
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans*=a[i]
        if ans>10**18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [float("inf")]*N
    dp[0] = 0
    for (s, t, c) in A:
        for j in range(s, t+1):
            dp[j-1] = min(dp[j-1], dp[s-1] + c)
    ans = dp[N-1]
#    print(dp)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

import math

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

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if not factor:
        return [n]
    else:
        factor.append(n)
        return factor

ans = 0
for i in A:
    ans += trial_division(i).count(2)

print(ans)


### FIXED CODE ###

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

ans = 0
for i in A:
    while True:
        if i%2 == 0:
            ans += 1
            i /= 2
        else:
            break

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

n,q=map(int,input().split())
s=input().replace("AC","10")
f=[1 if s[i]=="1" else 0 for i in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  print(sum(f[l-1:r-1]))


### FIXED CODE ###

n,q=map(int,input().split())
l=[0 for i in range(n)]
for i,v in enumerate(list(input().replace("AC","X!"))):
    l[i]=l[i-1]+(v=="!")
for c in range(q):
    h,m=map(int,input().split())
    print(l[m-1]-l[h-1])
### BUGGY CODE ###

a = int(input())

if a % 2 == 0:
	print('-1')
	exit()

n = 7
i = 0
while True:
	b = sum([(7 * (10**x)) for x in range(i + 1)])
	if b % a == 0:
		print(i + 1)
		exit()
	else:
		i = i + 1

### FIXED CODE ###

import sys


a = int(input())

cur = 0
for i in range(1, 10 ** 7):
	#b = sum([(7 * (10**x)) for x in range(i + 1)])
    cur *= 10
    cur += 7
    cur %= a
    if cur == 0:
        print(i)
        sys.exit()
print(-1)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for dy in Y[i+1:]:
        for k in range(n):
            rx = X[k]
            for lx in X[k+1:]:
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
ans = 0

for i in range(M - 1, -1, -1):
    maximum_rwd = 0
    maximum_id = 0
    for j in range(len(A)):
        # A[j]報酬までの時間、
        if A[j] <= M - i and maximum_rwd < B[j]:
            maximum_id = j
            maximum_rwd = B[j]
    if maximum_rwd > 0:
        ans += maximum_rwd
        A.pop(maximum_id)
        B.pop(maximum_id)
print(ans)

### FIXED CODE ###

import heapq

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

A = [[] for _ in range(M)]
Q = []

for _ in range(N):
	day, money = map(int, input().split())
	if day <= M:
		A[day - 1].append(money)

ans = 0

for i in range(0, M):
	for money in A[i]:
		heapq.heappush(Q, -money)
	# print(Q)
	if Q:
		ans += heapq.heappop(Q)
		
print(-ans)
### BUGGY CODE ###

from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h*w*4)
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dp[Id]:
                continue
            
            if x == xg and y == yg:
                return modCeil(cost)//k
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if 0 <= nx < h and 0 <= ny < w and field[nx][ny] == '.':
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    ans = dijkstra()
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

x, y = map(int, input().split())
n = (x + y) // 3
p = 10 ** 9 + 7
if (x + y) % 3 == 0:
    r = 0
    if x > y:
        x, y = y, x
    while True:
        if 2 * x == y:
            break
        r += 1
        x -= 2
        y -= 1
    print(comb(n, r, p))
else:
    print(0)

### FIXED CODE ###

def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

x, y = map(int, input().split())
n = (x + y) // 3
p = 10 ** 9 + 7
if (x + y) % 3 == 0 and max(x, y) <= 2 * min(x, y):
    r = 0
    if x > y:
        x, y = y, x
    a = (2 * x - y) // 3
    r = min(a, n - a)
    print(comb(n, r, p))
else:
    print(0)
### BUGGY CODE ###

N, M = (int(x) for x in input().split())
p = [0]*M
S = ["a"]*M
wa = 0
wapre = 0
ac = 0
index = []
for i in range(M):
  p[i], S[i] = (x for x in input().split())
for i in range(M):
  if S[i] == "AC" and p[i] not in index:
    ac = ac + 1
    index.append(p[i])
  elif S[i] == "WA" and p[i] not in index:
    wa = wa + 1
for i in range(M):
  if p[i] not in index:
    wa = wa-1
print(ac, wa)

### FIXED CODE ###

N,M=map(int,input().split())
A=[0]*N
B=[0]*N
pen=0
for i in range(M):
  p,S=input().split()
  if S=="AC":
    A[int(p)-1]=1
  elif S == "WA" and A[int(p)-1] == 0:
    B[int(p)-1] += 1
penalty=[A[i]*B[i] for i in range(N)]
print(sum(A),sum(penalty))
### BUGGY CODE ###

value_list = []
number_of_test = int(input())
while True:
	try:
		value = int(input())
		value_list.append(value)
		if value_list.count(value) == 2:
			value_list.remove(value)
			value_list.pop()
	except EOFError:
		break
print(len(value_list))

### FIXED CODE ###

import collections

cnt = int(input())
array = []
for i in range(cnt):
    array.append(int(input()))
cnt_dict = collections.Counter(array)

res = 0
for j in cnt_dict.values():
    if j % 2 != 0:
        res += 1
print(res)
### BUGGY CODE ###


s = input()
ans = 0
while "ABC" in s:
    ans += s.count("ABC")
    s = s.replace("ABC", "BCA")
print(ans)

### FIXED CODE ###


s = input()
i, ans, total = 0, 0, 0

while i < len(s) - 1:
    if s[i: i + 2] == "BC":
        ans += total 
        i += 2
    elif s[i] == "A":
        total += 1
        i += 1
    else:
        total = 0
        i += 1

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

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
def p_comb(a, b, c, d):
    a = 2**a - 1
    b = 2**b - 1
    c = 2**c - 1
    d = 2**d - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    
    
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)   


### FIXED CODE ###

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
from operator import itemgetter
def solve():
    p_list = XY[:]

    # y座標の圧縮
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    # xでソート
    p_list= sorted(p_list)

    # ある点が四角に含まれる場合の総数を求めるメソッド
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    # a,bを求める
    bit = Bit(N)
    ans = 0
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a = tmp
        b = i-tmp
        c = r-tmp-1
        d = (N-r+1)-(i-tmp)-1
        bit.add(r, 1)
        _a = power[a] - 1
        _b = power[b] - 1
        _c = power[c] - 1
        _d = power[d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()
### BUGGY CODE ###

def main():
    input()  # n
    array = [int(x) for x in input().split()]
    mod = 10 ** 9 + 7
    ans = 0
    for i, ai in enumerate(array):
        for aj in array[i + 1:]:
            ans += ai * aj
            ans %= mod
    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

from itertools import accumulate


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    acc = accumulate(array)
    mod = 10 ** 9 + 7
    ans = 0
    for i, ai in enumerate(acc):
        if i == n - 1:
            continue
        ans += ai * array[i + 1]
        ans %= mod
    return ans


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

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

ans=0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k==S:
        ans+=1
print(ans)

### FIXED CODE ###

import itertools

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

ans=0
for i in range(K+1):
  for j in range(K+1):
    if 0<=S-(i+j)<=K:
      ans+=1
print(ans)
### BUGGY CODE ###

n =int(input())
a = list(map(int,input().split()))
b = []
x = {}
def fx(x) :
    ans = 0
    for i in range(1,x):
        ans += i
    return ans
for i in a :
    if i in x :
        x[i] += 1
        if x[i] == 2:
            b.append(i)
    else :
        x[i] = 1
anskari = 0
for i in b :
    anskari += fx(x[i])
for i in a :
    if x[i] == 1:
        print(anskari)
    else :
        print(anskari - fx(x[i]) + fx(x[i]-1))

### FIXED CODE ###

n =int(input())
a = list(map(int,input().split()))
b = []
x = {}
def fx(x) :
    ans = 0
    for i in range(1,x):
        ans += i
    return ans
for i in a :
    if i in x :
        x[i] += 1
        if x[i] == 2:
            b.append(i)
    else :
        x[i] = 1
anskari = 0
for i in b :
    anskari += fx(x[i])
for i in a :
    if x[i] == 1:
        print(anskari)
    else :
        print(anskari - x[i] +1)
### BUGGY CODE ###

s=input()
n=int(input())
q=[]
for _ in range(n):
  q.append(input().split())
sw=True #奇数回文字列の前後を入れ替えているときFalseになる
for i in range(n):
  if q[i][0]=='1':
    sw = not sw
  else:
    if q[i][1]=='1' and sw==True:
      s = q[i][2]+s
    elif q[i][1]=='2' and sw==False:
      s = q[i][2]+s
    else:
      s+=q[i][2]
if sw:
  print(s)
else:
  s0=''
  for i in range(len(s)):
    s0+=s[len(s)-1-i]
  print(s0)


### FIXED CODE ###

s=input()
n=int(input())
q=[]
for _ in range(n):
  q.append(input().split())
sw=True #奇数回文字列の前後を入れ替えているときFalseになる
sl=''
sr=''
for i in range(n):
  if q[i][0]=='1':
    sw = not sw
  else:
    if q[i][1]=='1' and sw==True:
      sl += q[i][2]
    elif q[i][1]=='2' and sw==False:
      sl += q[i][2]
    else:
      sr +=q[i][2]

ans=''
if sw:
  for i in range(len(sl)):
    ans+=sl[len(sl)-1-i]
  print(ans+s+sr)
else:
  for i in range(len(sr)):
    ans+=sr[len(sr)-1-i]
  for i in range(len(s)):
    ans+=s[len(s)-1-i]
  print(ans+sl)
### BUGGY CODE ###

N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)


### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    t_ratio = TA[n][0]
    a_ratio = TA[n][1]
    # coeff = 1
    # while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
    #     coeff += 1
    # ↓
    coeff = max((t_ratio + t_votes - 1) // t_ratio,
                (a_ratio + a_votes - 1) // a_ratio)

    t_votes = coeff * t_ratio
    a_votes = coeff * a_ratio

print(t_votes + a_votes)
### BUGGY CODE ###

import math
k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(ans)



### FIXED CODE ###

import math
k=int(input())
ans=0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans+=math.gcd(math.gcd(a,b),c)
print(ans)