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

from collections import defaultdict

n = int(input())
s = list(input())
q = int(input())
ql = [input().split() for _ in range(q)]

w = 800
sl = []
dl = []
for i in range((n+w-1)//w):
    ss = s[i*w:min((i+1)*w,n)]
    dl.append(set(ss))
    sl.append(ss)
if len(dl)%2==1:
    dl.append(set())
dl2 = []
for i in range(len(dl)//2):
    dl2.append(dl[2*i] | dl[2*i+1])
for i in range(q):
    if ql[i][0]=="1":
        idx = int(ql[i][1])-1
        c = ql[i][2]

        ss = sl[idx//w]
        ss[idx%w] = c
        s[idx] = c
        sl[idx//w] = ss
        dl[idx//w] = set(ss)
        if (idx//w)%2==0:
            dl2[idx//w//2] = dl[idx//w] | dl[idx//w+1]
        else:
            dl2[idx//w//2] = dl[idx//w-1] | dl[idx//w]
    else:
        l = int(ql[i][1])-1
        r = int(ql[i][2])-1

        li = l//w
        ri = r//w
        if abs(li-ri)<2:
            print(len(set(s[l:r+1])))
        else:
            u = set(sl[li][l%w:])
            u |= set(sl[ri][:r%w+1])
            if (li+1)%2==1:
                u |= dl[li+1]
                li += 1
            if (ri-1)%2==0:
                u |= dl[ri-1]
                ri -= 1
            for j in range(li+1,ri,2):
                u |= dl2[j//2]
            print(len(u))


### FIXED CODE ###


class SegTree(object):
    """docstring for SegTree."""
    def __init__(self, l, _n):
        n = 1
        while n<_n:
            n *= 2
        self.n = n
        self.dat = [0 for _ in range(2*n)]
        for i in range(_n):
            self.dat[i+n-1] |= 1<<l[i]
        self.init(0)

    def init(self, i):
        if i>=self.n-1:
            return self.dat[i]
        self.dat[i] = self.init(self.left(i)) | self.init(self.right(i))
        return self.dat[i]

    def par(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def update(self, i, x):
        i += self.n-1
        self.dat[i] = 1<<x
        while i>0:
            i = self.par(i)
            self.dat[i] = self.dat[self.left(i)] | self.dat[self.right(i)]

    def q(self,a,b,k,l,r):
        if r<=a or b<=l:
            return 0
        if a<=l and r<=b:
            return self.dat[k]
        return self.q(a,b,self.left(k),l,(l+r)//2) | self.q(a,b,self.right(k),(l+r)//2,r)

    def query(self,a,b):
        return self.q(a,b,0,0,self.n)

n = int(input())
s = [ord(c)-ord("a") for c in input()]
q = int(input())
ql = [input().split() for _ in range(q)]

seg = SegTree(s,n)

for i in range(q):
    if ql[i][0]=="1":
        seg.update(int(ql[i][1])-1, ord(ql[i][2])-ord("a"))
    else:
        r = seg.query(int(ql[i][1])-1, int(ql[i][2]))
        print(bin(r).count("1"))
### BUGGY CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N]

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

for i in range(N):
    a,b = AB[i]
    for t in range(T):
        dp[i+1][t][0] = dp[i][t][0]
        dp[i+1][t][1] = dp[i][t][1][:]
        if t-a>=0:
            if dp[i+1][t][0] < dp[i][t-a][0] + b:
                dp[i+1][t][0] = dp[i][t-a][0]+b
                dp[i+1][t][1] = dp[i][t-a][1][:]
                dp[i+1][t][1].append(i)

ans0 = dp[N][-1][0]
ans = ans0
s = set(dp[N][-1][1])
for i in range(N):
    if i in s:continue
    ans = max(ans,ans0+AB[i][1])
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*N]

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

for i in range(N):
    a,b = AB[i]
    for t in range(T):
        dp[i+1][t] = dp[i][t]
        if t-a>=0:
            dp[i+1][t] = max(dp[i+1][t],dp[i][t-a]+b)

s = []
t = T-1
for j in range(N-1,-1,-1):
    a,b = AB[j]
    while (dp[j+1][t] == dp[j+1][t-1]) and t>0:
        t -= 1
    if dp[j+1][t] == dp[j][t]:
        pass
    else:
        t -= a
        s.append(j)

ans0 = dp[N][-1]
ans = ans0
for i in range(N):
    if s and i==s[-1] :
        s.pop()
        continue
    ans = max(ans,ans0+AB[i][1])
print(ans)
### BUGGY CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう

kouho = [x for x in set(A) if A.count(x) == 1]
target = kouho[:]

for i in range(len(A)):
    if target == []:
        break
    maxN = int(max(target)/A[i])
    for n in range(2,maxN+1):
        if A[i]*n in kouho:
            kouho.remove(A[i]*n)
            #print(A[i]*n)
target = kouho[:]

print(len(target))

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
### BUGGY CODE ###

from bisect import*
n,m,*a=map(int,open(0).read().split())
a.sort()
while m:insort(a,a.pop()//2);m-=1
print(sum(a))

### FIXED CODE ###

from heapq import*;n,m,*a=[-int(i)for i in open(0).read().split()];heapify(a);exec('heappush(a,0--heappop(a)//2);'*-m);print(-sum(a))
### BUGGY CODE ###

k, s = list(map(int, input().split()))
xyz_l = []
count = int(0)

for x in range(k+1)[::-1]:
    yz = s - x
    for y in range(k+1)[::-1]:
        z = yz - y
        if x >= y >= z >= 0:
            xyz_l.append([x, y, z])
            if len({x, y, z}) == 1:
                count += 1
            elif len({x, y, z}) == 2:
                count += 3
            else:
                count += 6

print(count)


### FIXED CODE ###

k, s = list(map(int, input().split()))
count = int(0)

for x in range(k+1)[::-1]:
    yz = s - x
    if yz > k*2:
        break
    for y in range(k+1)[::-1]:
        z = yz - y
        if x >= y >= z >= 0:
            if len({x, y, z}) == 1:
                count += 1
            elif len({x, y, z}) == 2:
                count += 3
            else:
                count += 6

print(count)
### BUGGY CODE ###

mod = 10**9+7
n=int(input())
A=list(map(int,input().split()))
ans = 0
for i,a in enumerate(A[:-1]):
  for j,a2 in enumerate(A[i:]):
    ans += a^a2
print(ans%mod)

### FIXED CODE ###

import numpy as np

mod = 10**9+7
n=int(input())
A=np.array(list(map(int,input().split())))
ans = 0

for i in range(60):
  n1 = np.count_nonzero((A>>i)&1)
  n0 = n-n1
  ans += (2**i)*n1*n0 % mod
ans %= mod
print(ans)
### BUGGY CODE ###

import sys
n, k = list(map(int, input().split()))

if (k == 1):
    print(0)
    sys.exit()

preN = n
while True:
    tmp = abs(n - k)
    if (tmp < n):
        n = tmp
    else:
        break

print(n)


### FIXED CODE ###

import sys
n, k = list(map(int, input().split()))

if (k == 1):
    print(0)
    sys.exit()

s, a = divmod(n, k)

t = k - a

if (a < t):
    print(a)
else:
    print(t)
### BUGGY CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math



def gcd_ab(a,b):
  while a != b:
    if a > b:
      a,b = [b,a]
    if a == 0:
      return b
    b = b-a
  return a


if __name__ == "__main__": 
  N = int(input())
  An = list(map(int, sys.stdin.readline().rstrip().split()))
  cuml = [An[0] for i in range(N)]
  cumr = [An[-1] for i in range(N)]

  for i in range(1, N):
    cuml[i] = gcd_ab(cuml[i-1], An[i])
    cumr[N-i-1] = gcd_ab(cumr[N-i], An[N-i-1])

  cuml = [0] + cuml + [0]
  cumr = [0] + cumr + [0]

  ans = 0
  for i in range(1,N+1):
    ans = max(ans, gcd_ab(cuml[i-1], cumr[i+1]))
  print(ans)

### FIXED CODE ###

# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


def gcd_ab(a,b):
  a,b = sorted([a,b])
  if a == 0:
    return b
  return gcd_ab(b%a, a)

if __name__ == "__main__": 
  N = int(input())
  An = list(map(int, sys.stdin.readline().rstrip().split()))
  cum = [[0,0] for i in range(N+2)]

  for i in range(N):
    cum[i+1][0] = gcd_ab(cum[i][0], An[i])
    cum[N-i][1] = gcd_ab(cum[N-i+1][1], An[N-i-1])

  ans = [0 for i in range(N)]
  for i in range(1,N+1):
    ans[i-1] = gcd_ab(cum[i-1][0], cum[i+1][1])
  print(max(ans))
### BUGGY CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect
from scipy.sparse.csgraph import shortest_path
import numpy as np

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result = shortest_path(np.array(A))
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))


### FIXED CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    info = copy.deepcopy(d)
    for i in range(len(info)):
        for l in range(len(info)):
            for k in range(len(info)):
                info[l][k] = min(info[l][k], info[l][i] + info[i][k])
    return info


MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result = warshall_floyd(A)
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))
### BUGGY CODE ###

N, Q = map(int, input().split())
AC = [0 for _ in range(N)]
flag_A = False
for i, s in enumerate(input()):
    if flag_A:
        if s == 'C':
            AC[i-1] = 1
        flag_A = False

    elif s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(sum(AC[l-1:r-1:]))


### FIXED CODE ###

N, Q = map(int, input().split())
AC = [None] * N
flag_A = False
cnt = 0
for i, s in enumerate(input()):
    AC[i] = cnt
    if flag_A:
        if s == 'C':
            cnt += 1
            AC[i] = cnt
        flag_A = False

    if s == 'A':
        flag_A = True

for q in range(Q):
    l, r = map(int, input().split())
    print(AC[r-1] - AC[l-1])
### BUGGY CODE ###

s, t = [input() for _ in range(2)]

for i in range(len(s)):
    if s[i] == t[i]:
        pass
    else:
        s_diff = s[i]
        t_diff = t[i]
        s = s.translate(str.maketrans({s_diff: t_diff, t_diff: s_diff}))

if s == t:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s = list(input())
t = list(input())
x = list(set(s))
y = list(set(t))
a = []
b = []

for i in range(len(set(s))):
    a.append(s.count(x[i]))
    
for j in range(len(set(t))):
    b.append(t.count(y[j]))
    
a.sort()
b.sort()

if a == b:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

#/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def readInput():
	return [int(i) for i in input().split(" ")]

(R, C) = readInput()
N = int(input())
rowIdx = list() 
colIdx = list()
grid = defaultdict(lambda:None)
rowGrid = defaultdict(list)
colGrid = defaultdict(list)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].append(c)
	colGrid[c].append(r)
	grid[(r, c)] = a 
	rowIdx.append(r)
	colIdx.append(c)

pairIdx = rowIdx.copy()	
for i in rowIdx:
	pairIdx.remove(i)
	for j in pairIdx:
		tempRow = set(rowGrid[i])
		tempPair = set(rowGrid[j])
		intersect = tempRow.intersection(tempPair)
		if (len(intersect) == 0):
			continue
		col = list(intersect)[0]
		diff = grid[(i, col)] - grid[(j, col)] 
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP == None and anchor < diff):
				print('No')
				exit()
			elif (anchorP != None and anchor - anchorP != diff):
				print('No')
				exit()
		tempPair.difference_update(tempRow)
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP == None and anchor < -diff):
				print('No')
				exit()
print('Yes')

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

k, s = list(map(int, input().split()))

count = 0

for p in range(k+1):
    for q in range(k+1):
        if p + q > s:
            break
        for r in range(k+1):
            t = p + q + r
            if t == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = list(map(int, input().split()))
count = 0

for p in range(k+1):
    for q in range(k+1):
        r = s-p-q
        if r>=0 and r<=k:
            count += 1

print(count)
### BUGGY CODE ###

S = list(input())
N = len(S)
dp = [[0] * 13 for _ in range(N+1)]
MOD = 10**9 + 7
s = S[0]
if s=='?':
    for k in range(10):
        dp[0][k] = 1
else:
    dp[0][int(s)] = 1
 

for i in range(1,N):
    s = S[i]
    if s=='?':
        for j in range(13):
            for k in range(10):
                tmp = (j*10 + k)%13
                dp[i][tmp] += dp[i-1][j]
                dp[i][tmp] %= MOD
    else:
        for j in range(13):
            tmp = (j*10 + int(s))%13
            dp[i][tmp] += dp[i-1][j]
            dp[i][tmp] %= MOD
            
print(dp[N-1][5])

### FIXED CODE ###

S = list(input())
N = len(S)
dp = [[0] * 13 for _ in range(N+1)]
MOD = 10**9 + 7
s = S[0]
if s=='?':
    for k in range(10):
        dp[0][k] = 1
else:
    dp[0][int(s)] = 1
 

for i in range(1,N):
    s = S[i]
    if s=='?':
        for j in range(13):
            for k in range(10):
                tmp = (j*10 + k)%13
                dp[i][tmp] += dp[i-1][j]
                dp[i][tmp] %= MOD
    else:
        for j in range(13):
            tmp = (j*10 + int(s))%13
            dp[i][tmp] += dp[i-1][j]
            dp[i][tmp] %= MOD
            
print(dp[N-1][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    L = 2*K
    state = [[[0, 0] for _ in range(L+1)] for _ in range(L+1)]

    for _ in range(N):
        x, y, c = map(str, input().split())
        if c == 'W':
            state[int(x)%L+1][int(y)%L+1][0] += 1
        else:
            state[int(x)%L+1][int(y)%L+1][1] += 1

    for i in range(L):
        for j in range(L):
            for k in [0, 1]:
                state[i+1][j+1][k] += state[i+1][j][k] + state[i][j+1][k] - state[i][j][k]

    ans = 0
    for x in range(K):
        for y in range(K):
            for k in [0, 1]:
                count = 0
                count += state[x][y][k]
                count += state[x+K][y+K][k] - state[x][y+K][k] - state[x+K][y][k] + state[x][y][k]
                count += state[L][y][k] - state[x+K][y][k]
                count += state[x][L][k] - state[x][y+K][k]
                count += state[L][L][k] - state[x+K][L][k] - state[L][y+K][k] + state[x+K][y+K][k]

                l = k ^ 1
                count += state[x+K][y][l] - state[x][y][l]
                count += state[x][y+K][l] - state[x][y][l]
                count += state[L][y+K][l] - state[x+K][y+K][l] - state[L][y][l] + state[x+K][y][l]
                count += state[x+K][L][l] - state[x+K][y+K][l] - state[x][L][l] + state[x][y+K][l]

                ans = max(ans, count)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    L = 2*K
    state = [[[0, 0] for _ in range(L+1)] for _ in range(K+1)]

    for _ in range(N):
        x, y, c = map(str, input().split())
        a, b = int(x)%L, int(y)%L
        k = 0 if c == 'W' else 1
        if a >= K:
            if b >= K:
                a -= K
                b -= K
            else:
                a -= K
                b += K
        state[a+1][b+1][k] += 1


    for i in range(K):
        for j in range(L):
            for k in [0, 1]:
                state[i+1][j+1][k] += state[i+1][j][k] + state[i][j+1][k] - state[i][j][k]

    ans = 0
    for x in range(K):
        for y in range(K):
            for k in [0, 1]:
                count = 0
                count += state[x][y][k]
                count += state[x][L][k] - state[x][y+K][k]
                count += state[K][y+K][k] - state[x][y+K][k] - state[K][y][k] + state[x][y][k]

                l = k ^ 1
                count += state[K][y][l] - state[x][y][l]
                count += state[x][y+K][l] - state[x][y][l]
                count += state[K][L][l] - state[K][y+K][l] - state[x][L][l] + state[x][y+K][l]

                ans = max(ans, count)
    print(ans)

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

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
# from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out = sys.stdout.write
# sys.setrecursionlimit(100000)
INF = int(1e9)
mod = int(1e9) + 7

n = int(data())
P = list(mdata())
dp = [0.0] * (n // 2 + 2)
dp[1] = float(1)
for i in range(n):
    for j in range(len(dp) - 1, 0, -1):
        dp[j] = dp[j - 1] * (1 - P[i]) + dp[j] * (P[i])
print(sum(dp))

### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))
### BUGGY CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
n,m = map(int,input().split())
if n == m:
    ans = P(n,n) * P(m,m) * 2
    print(ans)
elif abs(n-m) > 1:
    print(0)
else:
    ans = P(n,n)*P(m,m)
    print(ans)

### FIXED CODE ###

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
n,m = map(int,input().split())
mod = 10**9+7
if n == m:
    ans = P(n,n) * P(m,m) * 2
    print(ans%mod)
elif abs(n-m) > 1:
    print(0)
else:
    ans = P(n,n)*P(m,m)
    print(ans%mod)
### BUGGY CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for _ in range(q):
  p,x = map(int, input().split())
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])

### FIXED CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop()
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])
### BUGGY CODE ###

N = int(input())
S = [0] * N
for i in range(N):
    S[i] = str(input())

Sum = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        S1 = sorted(S[i])
        S2 = sorted(S[j])
        
        for k in range(10):
            if S1[k] != S2[k]:
                break
            if k == 9:
                Sum += 1

print(Sum)

### FIXED CODE ###

import math

N = int(input())
S = [0] * N
for i in range(N):
    S[i] = sorted(str(input()))

Sum = 0
hoge = 1

S.sort()

for i in range(N-1):
    if S[i] == S[i+1]:
        hoge += 1
    if (S[i] != S[i+1] or i == N-2) and hoge != 1:
        #Sum += math.factorial(hoge) // (math.factorial(hoge - 2) * math.factorial(2))
        Sum += hoge*(hoge-1)//2
        hoge = 1

print(Sum)
### BUGGY CODE ###

q, h, s, d = map(int, input().split())
n = int(input())
one = min(4*q, 2*h, s)
ans = n*one

for i in range(n//2+1):
    tmp = d*i+one*(n-2*i)
    ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

q, h, s, d = map(int, input().split())
n = int(input())
one = min(4*q, 2*h, s)

if d < one*2:
    print(d*(n//2)+one*(n%2))
else:
    print(one*n)
### BUGGY CODE ###

import sys
numbers = []
for line in sys.stdin:
	numbers.append(int(line))

answer = numbers[2] - numbers[1]

count = 1
while count < len(numbers) - 1:
	target = max(numbers[count + 1 : ])
	if target -  numbers[count] > answer :
		answer = target -  numbers[count]
	count += 1

print(answer)


### FIXED CODE ###

import sys
numbers = []
for line in sys.stdin:
	numbers.append(int(line))

answer = numbers[2] - numbers[1]
tmp_min = numbers[1]
for target in range(2, len(numbers)):
	answer =  max(numbers[target] - tmp_min ,answer)
	tmp_min = min(numbers[target] , tmp_min)

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

import sys

sys.setrecursionlimit(10000000)

class tree:
    def __init__(self):
        self.baby_list=[]
        self.counter=0
    
    def add_value(self, value):
        self.counter += value
        for i in self.baby_list:
            hoge[i].add_value(value)

N,Q=list(map(int, input().split() ))


hoge={}

for i in range(1,N+1):
    hoge[i] = tree()
    
for i in range(N-1):
    a,b=list(map(int, input().split() ))
    hoge[a].baby_list.append(b)

for i in range(Q):
    root, value = list(map(int, input().split() ))
    hoge[root].add_value(value)

output = []
for t in hoge:
    output.append(hoge[t].counter)

output = list(map(str, output))
print(" ".join(output))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10000000)


N,Q=list(map(int, input().split() ))

data={i+1:0 for i in range(N)}

# for i in range(N-1):
#     a,b=list(map(int, input().split() ))
#     hoge[a].baby_list.append(b)

relate = [list(map(int, input().split() )) for i in range(N-1)]
relate.sort(key=lambda x :x[0])
    
for i in range(Q):
    root, value = list(map(int, input().split() ))
    data[root]+=value

for a,b in relate:
    data[b]+=data[a]

print(" ".join(list(map(str,list(data.values())))))
### BUGGY CODE ###

def f():
    s = int(input())
    for i in range(int(s**0.5), -1, -1):
        if s%i == 0:
            x = i
            y = s//i
            break
    
    
    ans = [0, 0]
    ans.append(x)
    ans.append(0)
    ans.append(0)
    ans.append(y)
    print(*ans)

if __name__ == '__main__':
    f()

### FIXED CODE ###

def f():
    s = int(input())
    i9 = 10**9
    if s == i9 ** 2:
        print(i9, 0, 0, i9, 0, 0)
    else:
        print(i9 - (s%i9), s//i9 + 1, i9, 1, 0, 0)

if __name__ == '__main__':
    f()