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

def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
ans=[1 for i in range(N)]
for i in range(N):
  for j in range(i+1,N):
    if find(i)==find(j):
      if find2(i)==find2(j):
        ans[i]+=1
        ans[j]+=1
        
print(" ".join(map(str,ans)))

### FIXED CODE ###

from collections import Counter
def find(x):
  if x==Tree[x]:
      return x
  else:
      Tree[x]=find(Tree[x])
      return Tree[x]
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1!=s2:
    Tree[s2]=s1
def find2(x):
  if x==Tree2[x]:
      return x
  else:
      Tree2[x]=find2(Tree2[x])
      return Tree2[x]
def unite2(x,y):
  s1=find2(x)
  s2=find2(y)
  if s1!=s2:
    Tree2[s2]=s1
N,K,L=map(int,input().split())
Tree=[i for i in range(N)]
Tree2=[i for i in range(N)]
ans=[]
for i in range(K):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite(a,b)
for i in range(L):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  unite2(a,b)
l=[(find(i),find2(i)) for i in range(N)]
lc=Counter(l)
for i in range(N):
  ans.append(lc[l[i]])
print(" ".join(map(str,ans)))
### BUGGY CODE ###

n = int(input())
A = list(int(input()) for i in range(n))

for i in range(n):
    A_copy = A.copy()
    A_copy.pop(i)
    print(max(A_copy))

### FIXED CODE ###

import numpy as np

n = int(input())
A = np.array(list(int(input()) for i in range(n)))
A_sort = np.sort(A)
A_1 = A_sort[n-1]
A_2 = A_sort[n-2]


for i in range(n):
    if A[i] != A_1:
        print(A_1)
    else:
        print(A_2)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    gift = input()
    if not(gift in s):
        s.append(gift)
print(len(s))


### FIXED CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s.append(input())
print(len(Counter(s)))
### BUGGY CODE ###


n = int(input())
a = list(map(int, input().split()))

total = 1

for i in range(n):
    total *= a[i]

if total > 10 ** 18:
    print(-1)
else:
    print(total)



### FIXED CODE ###

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

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

if 0 in A:
    print(0)
    exit(0)

num = 1
for i in A:
    num *= i
    if num > 10**18:
        print(-1)
        exit(0)
print(num)
### BUGGY CODE ###

import math

monster_hp_list = []
monster_hp_list.append(int(input()))

count = 0

def floor_divide(hp_list):    
    return math.floor(hp_list/2)

while(monster_hp_list[0] != 1): 
    count += len(monster_hp_list)
    monster_hp_list = list(map(floor_divide,monster_hp_list))*2
    
    

count += len(monster_hp_list)
print(count)

### FIXED CODE ###

import math

monster_hp = int(input())
attack_count = 0

def attack_count_calc(monster_hp):
    if monster_hp == 1:                
        return attack_count + 1
    return attack_count + (2 * attack_count_calc(monster_hp//2) + 1)

print(attack_count_calc(monster_hp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[0]*4 for _ in range((R+1)*5000)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[i*5000+j][k] = dp[i*5000+j-1][k]
      #上から取らない
      dp[i*5000+j][0] = max(dp[i*5000+j][0],max(dp[(i-1)*5000+j]))
      if item[i-1][j-1]>0:
        #上からとる
        dp[i*5000+j][1] = max(dp[i*5000+j][1],max(dp[(i-1)*5000+j])+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[i*5000+j][k] = max(dp[i*5000+j][k],dp[i*5000+j-1][k-1]+item[i-1][j-1])
  ans = max(dp[R*5000+C])
  return ans
print(solve())

### FIXED CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())
### BUGGY CODE ###

N, P = map(int,input().split())
n, p = N, P

if(N == 1):
  print(P)
  exit()
elif(P == 1):
  print(1)
  exit()

num = []
s = 0
while s == 0:
  for i in range(2,p+1):
    if(p%i == 0):
      p = int(p/i)
      if(p == 1):
        s = 1
      num.append(i)
      break
d = {}
cnt = 1
for i in num:
  d[i] = num.count(i)
for k, v in d.items():
  if(v >= n):
    cnt *= k ** (v//n)
print(cnt)

### FIXED CODE ###

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

def calc(n):
  num = {}
  e, i = 0, 2
  while i**2 <= n:
    while n%i == 0:
      n //= i
      e += 1
    if(e > 0):
      num[i] = e
    i += 1
    e = 0
  return num

if(N == 1):
  print(P)
  exit()
elif(P == 1):
  print(1)
  exit()
else:
  cnt = 1
  for k, v in calc(P).items():
    if(v >= N):
      cnt *= k ** (v//N)
  print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
for m in range(M):
    A.append(int(input()))
    
dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

for i in range(N-1, -1, -1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007
    
print(dp[0])

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for m in range(M):
    A.append(int(input()))


broken = [0]*(N+2)
for a in A:
    broken[a] = 1

dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

for i in range(N-1, -1, -1):
    if broken[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007
    
print(dp[0])
### BUGGY CODE ###

def main():

    # Input N, Q
    N, Q = [int(c) for c in input().split()]

    # Input edges
    edges = [[] for i in range(N)]
    for i in range(N-1):
        u, v = [int(c)-1 for c in input().split()]
        edges[u].append(v)
        edges[v].append(u)

    # Form tree
    parent = [None for i in range(N)]
    childs = [[] for i in range(N)]
    def dfs(root):
        parent[root] = -1
        stack = [root]
        while stack:
            now = stack.pop()
            for nex in edges[now]:
                if parent[nex] is None:
                    parent[nex] = now
                    childs[now].append(nex)
                    stack.append(nex)
    dfs(0)

    # Queries
    incremented = [0 for i in range(N)]
    for i in range(Q):
        v, add = [int(c) for c in input().split()]
        v -= 1
        incremented[v] += add

    # Lower propagate
    total = [0 for i in range(N)]
    def propagate(root):
        stack = [root]
        while stack:
            now = stack.pop()
            total[now] += incremented[now]
            for child in childs[now]:
                total[child] += total[now]
                stack.append(child)
    propagate(0)

    # Print
    print(" ".join(str(num) for num in total))

main()


### FIXED CODE ###

def main():

    # Input N, Q
    N, Q = [int(c) for c in input().split()]

    # Input edges
    edges = [[] for i in range(N)]
    for i in range(N-1):
        u, v = [int(c)-1 for c in input().split()]
        edges[u].append(v)
        edges[v].append(u)

    # Form tree
    parent = [None for i in range(N)]
    childs = [[] for i in range(N)]
    def dfs(root):
        parent[root] = -1
        stack = [root]
        while stack:
            now = stack.pop()
            for nex in edges[now]:
                if parent[nex] is None:
                    parent[nex] = now
                    childs[now].append(nex)
                    stack.append(nex)
    dfs(0)

    # Queries
    incremented = [0 for i in range(N)]
    for i in range(Q):
        v, add = [int(c) for c in input().split()]
        v -= 1
        incremented[v] += add

    # Lower propagate
    total = [0 for i in range(N)]
    def propagate(root):
        stack = [root]
        while stack:
            now = stack.pop()
            total[now] += incremented[now]
            for child in childs[now]:
                total[child] += total[now]
                stack.append(child)
    propagate(0)

    # Print
    print(" ".join(str(num) for num in total))

main()
### BUGGY CODE ###

import copy
n = int(input())
l = sorted(list(map(int, input().split())))
b = []

def gcd(a,b):
	while b:
		a, b = b, a % b
	return a
if n == 2:
	print(max(l[0],l[1]))
elif n == 3:
	print(max(gcd(l[0],l[1]),gcd(l[0],l[2]),gcd(l[2],l[1])))
else:
	for i in range(n):
		tmp = copy.copy(l)
		tmp.pop(i)
		x = gcd(tmp[0],tmp[1])
		for j in list(range(2, n-1)):
			x = gcd(x,tmp[j])
		b.append(x)
	print(max(b))

### FIXED CODE ###

def gcd(a,b):
  while b:a,b=b,a%b
  return a
n,a,b=int(input()),list(map(int,input().split())),[]
if n==2:print(max(a[0],a[1]))
elif n==3:print(max(gcd(a[0],a[1]),gcd(a[0],a[2]),gcd(a[1],a[2])))
else:
  no,mi=a[0],a[0]
  for i in range(1,n):
    s=gcd(no,a[i])
    if s!=no:
      no=max(s,mi)
      mi=gcd(s,mi)
  print(no)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(1000000000)

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


def countPatty(N, X):

    if X == 0:
        return 0, 0

    if N == 0:
        return 1, X - 1

    # First inner burger
    nPatty, restX = countPatty(N - 1, X - 1)

    if restX == 1:
        nPatty, restX = nPatty + 1, 0
    elif restX >= 2:
        tPatty, restX = countPatty(N - 1, restX - 1)
        nPatty, restX = nPatty + tPatty + 1, restX - 1

    return nPatty, restX


nPatty, restX = countPatty(N, X)
print(nPatty)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

L, P = [1], [1]
for i in range(N - 1):
    L.append(L[-1] * 2 + 3)
    P.append(P[-1] * 2 + 1)


def countPatty(N, X):
    if N == 0:
        return 1 if X >= 1 else 0
    elif X <= 1:
        return 0
    elif 1 < X <= L[N - 1] + 1:
        return countPatty(N - 1, X - 1)
    elif L[N - 1] + 1 < X:
        return P[N - 1] + 1 + countPatty(N - 1, X - (L[N - 1] + 2))


print(countPatty(N, X))
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
indexlist = []
for i in range(len(S)-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            indexlist.append(i)
for LR in LRlist:
    L = LR[0]
    R = LR[1]
    answer = 0
    for i in indexlist:
        if L - 1 <= i <= R - 2:
            answer += 1
    print(answer)  

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
LRlist = []
for i in range(Q):
    LRlist.append(list(map(int,input().split())))
t = [0] * (N + 1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0) #t[i]=i文字目までのACのAの数：累積和
for LR in LRlist:
     L = LR[0]
     R = LR[1]
     print(t[R-1] - t[L-1])
### BUGGY CODE ###

import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

LV=(n-1).bit_length()
N0=2**LV
data=[0]*(2*N0)
lazy=[0]*(2*N0)

def gindex(l,r):
  L=l+N0;R=r+N0
  lm=(L//(L&-L))>>1
  rm=(R//(R&-R))>>1
  while L<R:
    if R<=rm:
      yield R
    if L<=lm:
      yield L
    L>>=1;R>>=1
  while L:
    yield L
    L>>=1

def propagates(*ids):
  for i in reversed(ids):
    v=lazy[i-1]
    if not v:
      continue
    lazy[2*i-1]+=v;lazy[2*i]+=v
    data[2*i-1]+=v;data[2*i]+=v
    lazy[i-1]=0

def update(l,r,x):
  L=N0+l;R=N0+r
  while L<R:
    if R&1:
      R-=1
      lazy[R-1]+=x;data[R-1]+=x
    if L&1:
      lazy[L-1]+=x; data[L-1]+=x
      L+=1
    L>>=1;R>>=1
  for i in gindex(l,r):
    data[i-1]=min(data[2*i-1],data[2*i])+lazy[i-1]

def query(l,r):
  propagates(*gindex(l,r))
  L=N0+l;R=N0+r

  s=10**9+1
  while L<R:
    if R&1:
      R-=1
      s=min(s,data[R-1])
    if L&1:
      s=min(s,data[L-1])
      L+=1
    L>>=1; R>>=1
  return s

x=[]
for i in range(n):
  x.append(l[i][0])
  update(i,i+1,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p,p+1)
  update(p,Right[p],-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  if p==n-1:
    break
  p+=1
  while query(p,p+1)<=0:
    p+=1
    if p==n:
      break
print(ans)

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()

data0=[0]*(n+1)
data1=[0]*(n+1)

def _add(data,k,x):
  while k<=n:
    data[k]+=x
    k+=k&-k

def add(l,r,x):
  _add(data0,l,-x*(l-1))
  _add(data0,r,x*(r-1))
  _add(data1,l,x)
  _add(data1,r,-x)

def _get(data,k):
  s=0
  while k:
    s+=data[k]
    k-=k&-k
  return s

def query(l,r):
  return _get(data1,r-1)*(r-1)+_get(data0,r-1)-_get(data1,l-1)*(l-1)-_get(data0,l-1)

x=[]
for i in range(n):
  x.append(l[i][0])
  add(i+1,i+2,l[i][1])

Right=[]
for i in range(n):
  Right.append(bisect.bisect_right(x,x[i]+2*d))

p=0
ans=0
while p<n:
  Q=query(p+1,p+2)
  add(p+1,Right[p]+1,-((Q+a-1)//a)*a)
  ans+=(Q+a-1)//a
  p=min(p+1,n-1)
  while query(p+1,p+2)<=0:
    p+=1
    if p==n:
      break
print(ans)
### BUGGY CODE ###

import sys
import fractions
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def solve():
    N = int(input())
    A = list(map(int, input().split()))

    lcm = A[0]
    for i in range(1, N):
        lcm = lcm * A[i] // fractions.gcd(lcm, A[i])

    B = [lcm // a for a in A]

    ans = 0
    for i in range(N):
        ans += B[i]
        ans %= mod

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import math
import fractions
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def factorize(n):
    b = 2
    fct = defaultdict(lambda: 0)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b = b + 1
    if n > 1:
        fct[n] += 1
    return fct


def divmod(x, mod=10**9 + 7):
    return pow(x, mod - 2, mod)


def solve():

    N = int(input())
    A = list(map(int, input().split()))
    B = [[1] for _ in range(N)]

    fac_list = defaultdict(lambda: 0)
    for i in range(N):
        d = factorize(A[i])
        for k, v in d.items():
            fac_list[k] = max(fac_list[k], v)

    lcm = 1
    for k, v in fac_list.items():
        lcm *= (k**v)
        lcm %= mod

    ans = 0
    for i in range(N):
        ans += divmod(A[i])
        ans %= mod

    ans *= lcm
    ans %= mod
    print(ans)


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

N, M = map(int, input().split())
items = list(map(int, input().split()))
for _ in range(M):
	items[items.index(max(items))] //= 2
print(sum(items))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
items = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(items)
for _ in range(M):
	tmp = heapq.heappop(items)
	heapq.heappush(items, int(tmp/2))
print(-sum(items))
### BUGGY CODE ###

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

### FIXED CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        f = math.gcd(a,b)
        for c in range(1, K+1):
            g = math.gcd(f,c)
            sumval += g
print(sumval)
### BUGGY CODE ###

def main():
  n=int(input())
  a = list(map(int,input().split()))
  ans=a[0]
  for i in range(1,n):
    ans*=a[i]
  if ans >1000000000000000000:
    ans=-1
  print(ans)
main()

### FIXED CODE ###

def main():
  n=int(input())
  a = list(map(int,input().split()))
  ans=a[0]
  if 0 in a:
    ans=0
  else:
    for i in range(1,n):
      ans*=a[i]
      if ans >1000000000000000000:
        ans=-1
        break
  print(ans)
main()
### BUGGY CODE ###

b=[]
b.append(1)
b.append(2)
count=1
s=0
while s<30:
    try:
        x=int(input())
        if x>b[count]:
            for i in range(b[count]+1,x+1):
                count1=0
                for j in range(2,i):
                    if i%j==0:
                        count1=1
                        break
                if count1==0:
                    count+=1
                    b.append(i)
            print(count)
        else:
            for i in range(count+1):
                if b[i]>x:
                    print(i-1)
                    break
                elif b[i]==x:
                    print(i)
                    break
        s+=1
    except EOFError:
        break

### FIXED CODE ###

str1=[0 for i in range(10**6)]
str1[0]=1
str1[1]=1
for i in range(2,(10**6)):
    if str1[i]==0:
        for j in range(2,(10**6)):
            if i*j>=len(str1):
                break
            else:
                str1[i*j]=1
            
while 1 :
    try:
        x=int(input())
        count=0
        for i in range(1,x+1):
            if str1[i]==0:
                count+=1
        print(count)
        
    except EOFError:
        break
### BUGGY CODE ###

from collections import Counter,deque
from scipy import special
S = input()
l = [int(n) for n in S]
a = [0]
t = 0
m = 1
d = deque(l)
while d:
    temp = d.pop()
    t += temp*m
    m *= 10
    a.append(t%2019)
b = [special.comb(kv,2,exact=True) for kv in Counter(a).values() if kv > 1]
print(sum(b))

### FIXED CODE ###

from collections import Counter,deque
from scipy import special
S = input()
l = [int(n) for n in S]
a = [0]
t = 0
m = 1
d = deque(l)
mod = 2019
while d:
    temp = d.pop()
    t = (t + (temp * m)) % mod
    m = (m * 10) % mod
    a.append(t%mod)
b = [special.comb(kv,2,exact=True) for kv in Counter(a).values() if kv > 1]
print(sum(b))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M,P = map(int,readline().split())
ABC = np.array(read().split(),np.int64)

A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

C = P-C

# bellman fordでAからBへの最短距離を求める

INF = 10**18
dist = np.full(N+1,INF,np.int64)
dist[1] = 0
for T in range(N+N+10):
    update = (dist[B] > dist[A] + C) & (dist[A] < INF)
    b = B[update]; a = A[update]; c = C[update]
    if T > N:
        dist[b] = -INF
    else:
        ind = (-dist[a]-c).argsort(); a=a[ind]; b=b[ind]; c=c[ind]
        dist[b] = dist[a] + c

assert dist[N] < INF

answer = -dist[N]
if answer < 0:
    answer = 0
elif answer == INF:
    answer = -1
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M,P = map(int,input().split())
ABC = [[int(x) for x in input().split()] for _ in range(M)]

INF = 10 ** 18
dist = [INF] * (N+1)
dist[1] = 0

loop = False
for i in range(2*N+100):
    for a,b,c in ABC:
        x = dist[a] + P - c
        if dist[b] > x:
            dist[b] = x
            if b == N and i > N:
                loop = True

if loop:
    answer = -1
else:
    answer = -dist[N]
    if answer < 0:
        answer = 0

print(answer)
### BUGGY CODE ###

import sys
import copy
input=sys.stdin.readline

n=int(input())
l=list(map(int,input().split()))
l.append(0)
l.insert(0,0)
#print(l)
dis=copy.deepcopy(l)
for i in range(1,n+2):
    dis[i]=abs(l[i]-l[i-1])
dis=dis[1:n+2]
#print(dis)
for i in range(n):
    print(sum(dis)-dis[i]-dis[i+1]+abs(l[i]-l[i+2]))

### FIXED CODE ###

import sys
import copy
input=sys.stdin.readline

n=int(input())
l=[0]+list(map(int,input().split()))+[0]
#print(l)
dis=copy.deepcopy(l)
a=0
for i in range(1,n+2):
    a+=abs(l[i]-l[i-1])
#print(dis)
for i in range(1,n+1):
    print(a-abs(l[i]-l[i-1])-abs(dis[i+1]-l[i])+abs(l[i-1]-l[i+1]))
### BUGGY CODE ###

k, q = map(int, input().split())
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= dd.count(0) * divq
    ans -= dd_r.count(0)

    last = x + sum(dd) * divq + sum(dd_r)
    ans -= last // m - x // m

    print(ans)


### FIXED CODE ###

import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), np.int64)
nxm = [map(int, input().split()) for _ in range(q)]

for n, x, m in nxm:
    dd = d % m

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

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

S = input()
Q = int(input())

c = 0
R = ""
L = ""
for _ in range(Q):
    T = input().split()
    if len(T) == 1:
        c +=1
        L_d = L
        L = "".join(list(reversed(R)))
        R = "".join(list(reversed(L_d)))
    else:
        if T[1] == "1":
            L = T[2] + L
        else:
            R = R + T[2]
if c % 2 == 0:
    print(L + S + R)
else:
    print(L + "".join(list(reversed(S))) + R)

### FIXED CODE ###

S = input()
Q = int(input())

c = 0
R = ""
L = ""
for _ in range(Q):
    T = input().split()
    if len(T) == 1:
        c +=1
    else:
        if T[1] == "1":
            if c % 2 == 0:
                L = T[2] + L
            else:
                R = R + T[2]
        else:
            if c % 2 == 0:
                R = R + T[2]
            else:
                L = T[2] + L
if c % 2 == 0:
    print(L + S + R)
else:
    print("".join(list(reversed(L+S+R))))
### BUGGY CODE ###

s = [i for i in input()]
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s = [c] + s
    else:
        s = s + [c]
        
if f:
    print(''.join(s[::-1]))
else:
    print(''.join(s))

### FIXED CODE ###

from queue import deque
s = deque([i for i in input()])
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s.appendleft(c)
    else:
        s.append(c)
        
if f:
    print(''.join(reversed(s)))
else:
    print(''.join(s))