Harryxun/stf_run huggingface dataset:
n, k = map(int,input().split())
a = list(map(int,input().split()))

route = []
i = 0

while True:
    ne = a[i]

    if i not in route:
        route.append(i)
    else:
        temp = len(route) - len(route[i:])
        print(a[(k-temp)%len(route[i:])])
        break

    i = ne - 1

### FIXED CODE ###

from collections import defaultdict

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

route = defaultdict(int)
i = 0
loop = []
tail = []

while route[i] < 2:

    if route[i] == 0:
        tail.append(i)
    else:
        loop.append(i)
    
    route[i] += 1
    i = a[i] - 1

if len(tail) > k:
    print(tail[k] + 1)
else:
    temp = len(tail) - len(loop)
    print(loop[(k-temp) % len(loop)] + 1)
N, M = (int(i) for i in input().split())
A = []
B = []
for i in range(N):
    A.append(input())
for i in range(M):
    B.append(input())

for i in range(N-M+1):
    if B[0] in A[i]:
        pos = A[i].find(B[j])
        flag = 0
        for j in range(M):
            if A[i+j][pos:pos+M] == B[j]:
                pass
            else:
                flag = -1
                break
        if flag = 0:
            print("Yes")

print("No")

### FIXED CODE ###

import sys

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

for i in range(N-M+1):
    if B[0] in A[i]:
        pos = A[i].find(B[0])
        flag = 0
        for j in range(M):
            if A[i+j][pos:pos+M] == B[j]:
                pass
            else:
                flag = -1
                break
        if flag == 0:
            print("Yes")
            sys.exit()

print("No")
a,b = map(int,input.split())
if a == b:
  ans = 'Draw'
elif a == 1:
  ans = 'Alice'
elif b == 1:
  ans = 'Bob'
elif a > b:
  ans = 'Alice'
else:
  ans = 'Bob'
print(ans)

### FIXED CODE ###

a,b = map(int,input().split())
if a == b:
  ans = 'Draw'
elif a == 1:
  ans = 'Alice'
elif b == 1:
  ans = 'Bob'
elif a > b:
  ans = 'Alice'
else:
  ans = 'Bob'
print(ans)
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    # 2 部グラフではなかったので、完全グラフから M を引いた値を出力する
    print(N*(N-1)//2-M)


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    # 2 部グラフではなかったので、完全グラフから M を引いた値を出力する
    print(N*(N-1)//2-M)
n, m = map(int, input().split())
s = []
for i in range(m):
    st = list(map(int, input().split()))
    s.append(st[1 :])
p = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    v = [1 - i for i in p]
    for j in range(m):
        if (i & (1 << j)):
            for t in s[j]:
                v[t - 1] = 1 - v[t - 1]
    if sum(v) == m:
        ans += 1
    #print(i, v)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
s = []
for i in range(m):
    st = list(map(int, input().split()))
    s.append(st[1 :])
p = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    al = True
    v = [bool(i & (1 << x)) for x in range(n)]
    for j in range(m):
        num = 0
        for t in s[j]:
            num += v[t - 1]
        if p[j] != num % 2:
            al = False
    ans += al
print(ans)
N = int(input())
is81 = false
for i in range(1, 10):
    for j in range(1, 10):
        if i*j == N:
            is81 = True

if is81:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
is81 = False
for i in range(1, 10):
    for j in range(1, 10):
        if i*j == N:
            is81 = True

if is81:
    print('Yes')
else:
    print('No')
input = input()
input = input.strip()
input = input.split(" ")
result = ""
for i in input:
    result += i[0].upper()
return result

### FIXED CODE ###

strs = raw_input()
strs = strs.split()
print strs[0][0].upper() + strs[1][0].upper() + strs[2][0].upper()
S=list(int(i) for i in input().split())
for x in range(len(S)-1):
  if S[x]==S[x+1]:
    print('Bad')
  break
  else:
    print('Good')


### FIXED CODE ###

S=list(int(i) for i in input())
for i in range(len(S)-1):
  if S[i]==S[i+1]:
    print('Bad')
    break
else:
  print('Good')
l=map(int(),raw_input().split())
c=l[0]*l[1]
if c%2==1:
  print('Odd')
else:
  print('Even')

### FIXED CODE ###

a, b=(int(i) for i in input().split())
c=a*b
if c%2==1:
  print('Odd')
else:
  print('Even')
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderDictionary[sum] = remainderDictionary.get(sum,0) + 1

ansDictionary = {1:0,2:1,3:3,4:6,5:10,6:15,7:21,8:28,9:36,10:45,11:55,12:66,13:78,14:91,15:105,16:120,17:136,18:153,19:171,20:190,21:210,22:231,23:253,24:276,25:300,26:325,27:351,28:378,29:406,30:435,31:465,32:496,33:528,34:561,35:595,36:630,37:666,38:703,39:741,40:780,41:820,42:861,43:903,44:946,45:990,46:1035,47:1081,48:1128,49:1176,50:1225,51:1275,52:1326,53:1378,54:1431,55:1485,56:1540,57:1596,58:1653,59:1711,60:1770,61:1830,62:1891,63:1953,64:2016}

ans = 0
for i in remainderDictionary:
  ans += ansDictionary[ remainderDictionary[i] ]
print(ans)

### FIXED CODE ###

number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum += int(i) * x
  sum %= 2019
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)
from sys import stdin

S, T = stdin.readline().rstrip().split()

print(T+S)
from sys import stdin

S, T = stdin.readline().rstrip().split()

print(T+S)


### FIXED CODE ###

from sys import stdin

S, T = stdin.readline().rstrip().split()

print(T+S)
from math import *
N=int(input())
A=list(map(int,input().split()))
l=[[],[],[]]
ans=1
p=10**9+7
for i in range(N):
    cnt=0
    piv=A[i]
    ind=[]
    for j in range(3):
        if len(l[j])==piv:
            cnt=cnt+1
            ind.append(j)
    l[ind[0]].append(piv)
    ans=(ans*cnt)%p
    #print(l,ans)
    #input()
print(ans)




### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
l=[[] for _ in range(3)]
ans=1
p=10**9+7
flag=1
for i in range(N):
    cnt=0
    piv=A[i]
    ind=[]
    for j in range(3):
        if len(l[j])==piv:
            cnt=cnt+1
            ind.append(j)
    if len(ind)==0:
        flag=0
        break
    l[ind[0]].append(piv)
    ans=(ans*cnt)%p
    #print(l,ans)
    #input()
if flag==1:
    print(ans%p)
else:
    print(flag)
dic = {}

def getX(x, y, cards, idx):
    if len(cards)==1:
        return abs(cards[0]-y)
    lgst = 0
    tmpcards = cards.copy()
    for ex, i in enumerate(cards):
        if(ex==len(cards)-1):
            return max(abs(i-y),lgst)
        tmpcards.remove(i)
        idx += 1
        #if (i,y,idx) in dic:
            #tmp = dic[(i,y,idx)]
        #else:
        tmp = getY(i, y, tmpcards, idx)
            #dic[(i,y,idx)]= tmp
        if tmp > lgst:
            lgst = tmp
    return lgst

def getY(x, y, cards, idx):
    if len(cards)==1:
        return abs(cards[0]-x)
    smlst = 0
    tmpcards = cards.copy()
    for ex, i in enumerate(cards):
        if (ex==len(cards)-1):
            return min(abs(i - x), smlst)
        tmpcards.remove(i)
        idx += 1
        #if (x,i,idx) in dic:
            #tmp = dic[(x,i,idx)]
        #else:
        tmp = getX(x, i, tmpcards, idx)
            #dic[(x,i,idx)]= tmp
        if tmp < smlst:
            smlst = tmp
    return smlst

n, z, w = map(int, input().split())
cards = list(map(int, input().split()))
print(getX(z, w, cards, 0))

### FIXED CODE ###

n, z, w = map(int, input().split())
cards = list(map(int, input().split()))
#print(getX(z, w, cards, 0))
if(abs(cards[len(cards)-1]-w)>abs(cards[len(cards)-1]-cards[len(cards)-2])):
    print(abs(cards[len(cards)-1]-w))
else:
    print(abs(cards[len(cards)-1]-cards[len(cards)-2]))
import collections
n,m = map(int, input().split())

friends = [0] * n
query = []

for i in range(m):
  a,b = map(int, input().split())
  if friends[a - 1] == 0 and  friends[b - 1] == 0:
    friends[a - 1] = tmp
    friends[b - 1] = tmp
    tmp += 1
  elif friends[a - 1] == 0:
    friends[a - 1] = friends[b - 1]
  elif friends[b - 1] == 0:
    friends[b - 1] = friends[a - 1]
  else:
    index_num = [n for n, v in enumerate(friends) if v == friends[a - 1]]
    duplicated = friends[b - 1]
    for i in index_num:
      friends[i] = duplicated

counted = collections.Counter(friends)
if counted.most_common()[0][1] != 0:
  print(counted.most_common()[0][1])
else:
  print(counted.most_common()[0][2])

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
  a,b = map(int, input().split())
  uf.union(a-1, b-1)

ans = 0
for i in range(n):
  ans = max(uf.size(i),ans)
  
print(ans)
# -*- coding: utf-8 -*-
a = int(input())
b = int(input().split(""))
list(b)
count = []
for i in range(a):
  count[i] = 0
  c = count[i]
  d = b[i]
  while d % 2 == 0:
    d = d / 2
    c += 1
    count[i] = c
print(min(count))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
count = []
for i in range(n):
    count.append(0)
    while a[i] % 2 == 0:
        a[i] = a[i] / 2
        count[i] += 1
print(min(count))
import math
a,b,c= map(int,input().split())


if math.sqrt(a)+math.sqrt(b)<math.sqrt(c):
    print('Yes')
else
    print('No')


### FIXED CODE ###

a,b,c=map(int,input().split())
print("Yes" if 4*a*b<(c-a-b)**2 and (c-a-b)>0 else "No")
n = int(input())
a = list(map(int,input().split()))
b = []
wk = wk1 = 0

for i in range(n):
    if a[i]%2 == 0:
        b.append(a[i])

for j in range(len(b)):
    if b[j]%3 == 0 or b[j]%5 == 0:
        wk = 1
    else:
        wk1 = 1
if wk1 == 1:
    print('DENIED')
else:5
    print('APPROVED')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
wk = wk1 = 0

for i in range(n):
    if a[i]%2 == 0:
        b.append(a[i])

for j in range(len(b)):
    if b[j]%3 == 0 or b[j]%5 == 0:
        wk = 1
    else:
        wk1 = 1
if wk1 == 1:
    print('DENIED')
else:
    print('APPROVED')
a, b, c, d, e, f = map(int, input().split())
res = None
m = 0
for aa in range(0, f, 100 * a):
    for bb in range(0, f, 100 * b):
        w = aa + bb
        if w == 0 or aa + bb > f:
            continue
        r = f - w
        for cc in range(0, r, c):
            for dd in range(0, r, d):
                s = cc + dd
                if s + w > f or 100 * s > e * w:
                    continue
                mm = s / w
                if mm > m:
                    res = (w + s, s)
                    m = mm
print(*res)

### FIXED CODE ###

a, b, c, d, e, f = map(int, input().split())
res = (100 * a, 0)
for aa in range(0, f + 1, 100 * a):
    for bb in range(0, f + 1, 100 * b):
        w = aa + bb
        if w == 0 or w >= f:
            continue
        r = f - w
        for cc in range(0, r + 1, c):
            for dd in range(0, r + 1, d):
                s = cc + dd
                t = w + s
                if t > f or 100 * s > e * w:
                    continue
                if s * res[0] > res[1] * t:
                    res = (t, s)
print(*res)
n = input()
print(n // 3)

### FIXED CODE ###

n = int(input())
print(int(n / 3))
a = input()
b = input()

if a == b:
 print("EQUEAL")
elif a > b:
 print("GREATER")
else:
 print("LESS")

### FIXED CODE ###

print("".join([s[0].upper() for s in input().split()]))
a[0],a[1],a[2] = map(int, raw_input().split())

i = 1
while i < 3 :
    j = i - 1
    while j > 0:
        if a[j] > a[j+1]:
             t = a[j]
             a[j] = a[j+1]
             a[j+1] = t
        else:
            break
        j -= 1
    i += 1

print a[0],a[1],a[2]

### FIXED CODE ###

a,b,c = sorted(map(int, raw_input().split()))
print a,b,c
x,a,b = map(int, input().split())
if a => b:
    print("delicious")    
elif b <= x + a:
    print("safe")
else:
    print("dangerous")

### FIXED CODE ###

x,a,b = map(int, input().split())
if a >= b:
    print("delicious")    
elif b <= x + a:
    print("safe")
else:
    print("dangerous")
n = int(input())
s = list(input())
#
ans = 0
def R(x):
    if x == 0:
        if s[0] == 'R':
            return 1
        else:
            return 0
    else:
        if s[x] == 'R':
            return R(x-1) + 1
        else:
            return R(x-1)
def B(x):
    if x == 0:
        if s[0] == 'B':
            return 1
        else:
            return 0
    else:
        if s[x] == 'B':
            return B(x-1) + 1
        else:
            return B(x-1)
def G(x):
    if x == 0:
        if s[0] == 'G':
            return 1
        else:
            return 0
    else:
        if s[x] == 'G':
            return G(x-1) + 1
        else:
            return G(x-1)

for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            if s[i] != 'R' and s[j] != 'R':
                if 2*j-i <= n-1 and s[2*j-i] == 'R':
                    ans += R(n-1) - R(j) - 1
                else:
                    ans += R(n-1) - R(j)
            elif  s[i] != 'B' and s[j] != 'B':
                if 2*j - i <= n-1 and s[2*j-i] == 'B':
                    ans += B(n-1) - B(j) - 1
                else:
                    ans += B(n-1) - B(j)
            elif s[i] != 'G' and s[j] != 'G':
                if 2*j - i <= n-1 and s[2*j-i] == 'G':
                    ans += G(n-1) - G(j) - 1
                else:
                    ans += G(n-1) - G(j)
        else:
            pass
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

ans = r_cnt*g_cnt*b_cnt

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[i] != s[k] and s[j]!=s[k]:
            ans -= 1
print(ans)
A,B,C = map(int,input().split())
print(if(B/A <= C)int(B/A) else(int(C))

### FIXED CODE ###

A,B,C = map(int,input().split())

ans = min(C,B//A)
print(ans)
n,m=map(int,input().split())
def yak1(n,m):
  l=[]
  for i in range(1,min(int((m)**1/2),m//n)+1):
    if m%i==0:
      l.append(i)
      if m//(m//i)!=m/i and m//(m//i)>=m/n:
        l.append(m//i)
  return l
print(max(yak1(n,m)))     

### FIXED CODE ###

def make_divisors(n,m):
    divisors = []
    for i in range(1,min(int(m**(1/2))+1,int(m//n)+1)):
      if m % i == 0:
          divisors.append(i)
          if i != m // i and m//i<=m//n:
              divisors.append(m//i)
    return divisors
n,m=map(int,input().split())
print(max(make_divisors(n,m)))
a,b,c,d = map(int, input().split()
if a + b > c +d:
	print('Left')
elif a+b == c+d:
	print('Balanced')
else:
	print('Right')

### FIXED CODE ###

a,b,c,d = map(int, input().split())
if a + b > c +d:
	print('Left')
elif a+b == c+d:
	print('Balanced')
else:
	print('Right')
x, n = map(int,input().split())
p = list(map(int,input().split()))
p_list = [0 for i in range(100)]
n_abs = 1000
ans = 100000

for i in p:
    p_list[i-1] = 1

for i in range(0, 102):
    if i == 0:
        temp_abs = abs(x-i)
        if n_abs > temp_abs:
            n_abs = temp_abs
            ans = i
    else:
        temp_abs = abs(x-i)
        if n_abs > temp_abs and p_list[i-1] != 1:
            n_abs = temp_abs
            ans = i
        elif n_abs == temp_abs and i < ans and p_lsit[i-1] != 1:
            n_abs = temp_abs
            ans = i

print(ans)


### FIXED CODE ###

x, n = map(int,input().split())
p = list(map(int,input().split()))
p_list = [0 for i in range(100)]
n_abs = 1000
ans = 100000

for i in p:
    p_list[i-1] = 1

for i in range(0, 102):
    if i == 0 or i == 101:
        temp_abs = abs(x-i)
        if n_abs > temp_abs:
            n_abs = temp_abs
            ans = i
    else:
        temp_abs = abs(x-i)
        if n_abs > temp_abs and p_list[i-1] != 1:
            n_abs = temp_abs
            ans = i
        elif n_abs == temp_abs and i < ans and p_lsit[i-1] != 1:
            n_abs = temp_abs
            ans = i

print(ans)
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
x = input()
c = x.count('1')

y = 0
for i in range(n):
    y += int(x[i])*2**(n-1-i)
a = [-1]*(y+1)
a[0] = 0
a[1] = 1

for i in range(n):
    ans = 0
    if x[i] == '0':
        c_tmp = c + 1
        y_tmp = y + 2**(n-1-i)
    else:
        c_tmp = c - 1
        y_tmp = y - 2**(n-1-i)
    reg = y_tmp
    while y_tmp != 0:
        ans += 1
        y_tmp = y_tmp % c_tmp
        c_tmp = format(y_tmp,'b').count('1')
        try:
            if 0 < y_tmp < n and a[y_tmp] != -1:
                ans += a[y_tmp]
                break
        except:
            continue
    print(ans)
    try:
        a[reg] = ans
    except:
        continue

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    N = INT()
    xbin = input()
    xdec = int(xbin, 2)
    m = xbin.count('1')

    a = xdec % (m+1)
    b = xdec % (m-1) if m > 1 else 0

    num = [0]*N
    for i in range(1, N):
        num[i] = num[i % bin(i).count('1')] + 1

    for i in range(N):
        if xbin[i] == '0':
            y = ( a + pow(2, N-i-1, m+1) ) % ( m+1 )
            print(num[y] + 1)
        elif m <= 1:
            print(0)
        else:
            y = ( b - pow(2, N-i-1, m-1) ) % ( m-1 )
            print(num[y] + 1)

if __name__ == '__main__':
    solve()
import sys
import math
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

A, B, C, D = MAP()
# Cで割り切れる数 = B/C - A/C
c_b = B//C
c_a = A//C if A%C else A//C-1
c = c_b-c_a

d_b = B//D
d_a = A//D if A%D else A//D-1
d = d_b-d_a

E = (C*D) // (math.gcd(C,D))
#print(E)
e_b = B//E
e_a = A//E if A%E else A//E-1
e = e_b - e_a

#print(c, d, e)

print((B-A+1)-(c+d-e))

### FIXED CODE ###

import sys
import fractions
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

A, B, C, D = MAP()
# Cで割り切れる数 = B/C - A/C
c_b = B//C
c_a = A//C if A%C else A//C-1
c = c_b-c_a

d_b = B//D
d_a = A//D if A%D else A//D-1
d = d_b-d_a

E = (C*D) // (fractions.gcd(C,D))
#print(E)
e_b = B//E
e_a = A//E if A%E else A//E-1
e = e_b - e_a

#print(c, d, e)

print((B-A+1)-(c+d-e))
input()
if s == 'SUN':
  print('7')
elif s == 'MON':
  print('6') 
elif s == 'TUE':
  print('5') 
elif s == 'WED':
  print('4')
elif s == 'THU':
  print('3')
elif s == 'FRI':
  print('2')
else:
  print('1') 

### FIXED CODE ###

s=input()
if s == 'SUN':
  print('7')
elif s == 'MON':
  print('6') 
elif s == 'TUE':
  print('5') 
elif s == 'WED':
  print('4')
elif s == 'THU':
  print('3')
elif s == 'FRI':
  print('2')
else:
  print('1')
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))


### 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())