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

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

def solve():
    N, MOD = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        adjL[x].append(y)
        adjL[y].append(x)

    dp = [[] for _ in range(N)]
    outdegs = [0] * N
    iPars = [-1] * N
    def dfsDP(v, vPar):
        outdeg = outdegs[v] = len(adjL[v])
        dp[v] = [0] * outdeg
        res = 1
        for i, v2 in enumerate(adjL[v]):
            if v2 == vPar:
                iPars[v] = i
                continue
            dp[v][i] = dfsDP(v2, v)
            res = res * dp[v][i] % MOD
        return (res + 1) % MOD

    anss = [0] * N
    def dfsAns(v, vPar, resPar):
        if vPar != -1:
            dp[v][iPars[v]] = resPar

        outdeg = outdegs[v]
        dpL = [1] * (outdeg+1)
        for i in range(outdeg):
            v2 = adjL[v][i]
            dpL[i+1] = dpL[i] * dp[v][i] % MOD
        dpR = [1] * (outdeg+1)
        for i in reversed(range(outdeg)):
            v2 = adjL[v][i]
            dpR[i] = dpR[i+1] * dp[v][i] % MOD
        anss[v] = dpL[-1]

        for i, v2 in enumerate(adjL[v]):
            if v2 == vPar: continue
            dfsAns(v2, v, (dpL[i] * dpR[i+1] + 1) % MOD)


    dfsDP(0, -1)
    dfsAns(0, -1, 0)

    print('\n'.join(map(str, anss)))


solve()


### FIXED CODE ###

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

N, MOD = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    adjL[x].append(y)
    adjL[y].append(x)

def ReRooting(adjL):
    def merge(val1, val2):
        return val1 * val2 % MOD
    def calcValue(val1):
        return (val1 + 1) % MOD

    numV = len(adjL)
    vRoot = 0
    useds = [False] * numV
    useds[vRoot] = True
    vs = [vRoot]
    pars = [-1] * numV
    stack = [vRoot]
    while stack:
        v = stack.pop()
        for v2 in adjL[v]:
            if not useds[v2]:
                useds[v2] = True
                vs.append(v2)
                pars[v2] = v
                stack.append(v2)

    anss = [0] * numV
    dpUpFrom, dpDownTo, accLs, accRs = [1]*numV, [1]*numV, [1]*numV, [1]*numV
    for v in reversed(vs):
        vPar = pars[v]
        tmp = 1
        for v2 in adjL[v]:
            if v2 == vPar: continue
            accLs[v2] = tmp
            tmp = merge(tmp, dpUpFrom[v2])
        tmp = 1
        for v2 in reversed(adjL[v]):
            if v2 == vPar: continue
            accRs[v2] = tmp
            tmp = merge(tmp, dpUpFrom[v2])
        anss[v] = tmp
        dpUpFrom[v] = calcValue(tmp)

    for v in vs:
        vPar = pars[v]
        dpDownToV = dpDownTo[v]
        anss[v] = merge(anss[v], dpDownToV)
        for v2 in adjL[v]:
            if v2 == vPar: continue
            tmp = merge(accLs[v2], accRs[v2])
            tmp = merge(tmp, dpDownToV)
            dpDownTo[v2] = calcValue(tmp)
    return anss

anss = ReRooting(adjL)
print('\n'.join(map(str, anss)))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
 
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b
 
 
s = [int(input()) for i in range(M)]
broken = []
broken.append(-1)
broken.extend(s)
broken.append(N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に
 
gaps = []  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps.append(broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break
 
 
fibs = []
if flag == 1:
    print(0)
else:
    for i in range(max(gaps)):
        fibs.append(fib(i))
        
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
s = list(map(int, input().split()))
N = s[0]
M = s[1]
flag = 0
def fib(n):
    a, b = 0, 1
    c = [1]
    for i in range(n):
        a, b = b, a + b
        c.append(b)
    return c


broken = np.array([int(input()) for i in range(M)])
broken = np.append(-1,broken)
broken = np.append(broken,N+1)
#  -1段目とN+1段目が壊れていると表記して一貫した計算が可能に

gaps = np.array([])  # 壊れている段の間にある壊れていない段数
for i in range(M+1):
    gaps = np.append(gaps, broken[i+1]-broken[i]-1)
    if broken[i+1]-broken[i]-1 == 0:
        flag = 1
        break

gaps = np.array(gaps, np.int)  # 整数列に変換



if flag == 1:
    print(0)
else:
    fibs = fib(max(gaps))
    patterns = 1
    for i in range(len(gaps)):
        patterns *= fibs[gaps[i]-1]
    print(patterns % 1000000007)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0], x[1]))
xh = deque(xh)
cnt = 0
while xh:
    c = xh.popleft()
    cx, ch = c[0], c[1]
    if ch <= 0:
        continue
    cn = (ch + a - 1) // a
    cnt += cn
    tmp = []
    i = 0
    while xh and i < len(xh):
        nx = xh[i][0]
        if nx <= cx + 2*d:
            xh[i][1] -= cn * a
            i += 1
        else:
            break
    
print(cnt)

### FIXED CODE ###

from collections import deque
import sys

input = sys.stdin.buffer.readline
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, d, a = MAP()
xh = [LIST() for i in range(n)]

xh = sorted(xh, key=lambda x:(x[0]))
q = deque()
ca = 0
cnt = 0
for i in range(n):
    cx, ch = xh[i][0], xh[i][1]
    
    while q and q[0][0] < cx:
        qx, qa = q.popleft()
        ca -= qa
    
    if ch - ca <= 0:
        continue
    
    cn = (ch - ca + a - 1) // a
    cnt += cn
    ca += cn * a
    q.append([cx+2*d, cn*a])
    
print(cnt)
### BUGGY CODE ###

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

for i in range(N, M + 1):
    if M % i == 0:
        print(M // i)
        exit()


### FIXED CODE ###

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


def get_divisor(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if n // i != i:
                divisors.append(n // i)

    return sorted(divisors)


divisors = get_divisor(M)
for d in divisors:
    if d >= N:
        print(M // d)
        exit()

print(1)
### BUGGY CODE ###

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


MOD = 1000000007

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

dp[0] = 1

for index in range(N):
    current = index + 1
    if current in A:
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

print(dp[-1]%MOD)







### FIXED CODE ###

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


MOD = 1000000007

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

dp[0] = 1



next_ng_index = 0

for index in range(N):
    current = index + 1
    if current == A[next_ng_index]:
        next_ng_index += 1
        continue

    pre_stair = current - 1
    dp[current] += dp[pre_stair]

    prepre_stair = current -2
    if prepre_stair >= 0:
        dp[current] += dp[prepre_stair]

    dp[current] %= MOD

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

R,G,B,N = list(map(int,input().split()))

cnt = 0

for r in range(int(N/R)+1):
    for g in range(int(N/G)+1):
        for b in range(int(N/B)+1):
            if R*r + G*g + B*b == N:
                cnt += 1

print(cnt)

### FIXED CODE ###

R,G,B,N = list(map(int,input().split()))

cnt = 0
sum = 0

for r in range(int(N/R)+1):
    sum = R*r
    for g in range(3001):
        if sum + G*g > N:
            break
        if (N-sum-(G*g))%B == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

# coding: utf-8
n, k = map(int, input().split())
p =list(map(int,input().split()))
pp =[]
for i in range(len(p) - k + 1):
  tmp = 0
  for j in range(k):
    tmp += p[i+j]
  pp.append(tmp)
mn = max(pp)
ans = (mn + k) / 2
print(ans)

### FIXED CODE ###

# coding: utf-8
n, k = map(int, input().split())
p = list(map(int, input().split()))
pm = pp = sum(p[0:k])
for i in range(n - k):
    pp = pp - p[i] + p[k+i]
    pm = pp if (pp >= pm) else pm
ans = (pm + k) / 2
print(ans)
### BUGGY CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D<H*W
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

### FIXED CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])
### BUGGY CODE ###

N=int(input())

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

B=max(A)

answer=10**9

for j in range(-B,B+1):
	total=0
	for i in range(len(A)):
		total=total+abs(A[i]-(i+j))
	answer=min(total,answer)
print(answer)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
import statistics
B=[0]*N
answer=0
for i in range(N):
	B[i]=A[i]-(i+1)
med=int(statistics.median(B))

for i in range(N):
	answer+=(abs(B[i]-med))
print(answer)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

t = S()
l = len(t)
ans = ""
for s in t:
    if s == '?':
        ans += 'D'
    else:
        ans += s
print(ans)


### FIXED CODE ###

t = input()
l = len(t)
ans = ""
for s in t:
    if s == '?':
        ans += 'D'
    else:
        ans += s
print(ans)
### BUGGY CODE ###

n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
aa=[]
ans=defaultdict(int)
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    ac=Counter(a)
    aa.append(ac)

for i in range(len(aa)):
    for a in aa[i].keys():
        ans[a]+=aa[i][a]

for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
from copy import deepcopy
dist=dijkstra_heap(0)
distx=dijkstra_heap(x-1)
disty=dijkstra_heap(y-1)
counts=[]
for i in range(n-1):
    if i<x-1:
        tmp=[d-i for d in dist[i:]]
        counts.append(Counter(tmp))
    elif x-1<=i<y-1:
        tmp=[min(distx[i]+distx[d], disty[i]+disty[d], abs(d-i)) for d in range(i,n)]
        counts.append(Counter(tmp))
    else:
        tmp=[disty[d]-disty[i] for d in range(i,n)]
        counts.append(Counter(tmp))
ans=defaultdict(int)

for i in range(n-1):
    keys=counts[i].keys()
    for kk in keys:
        ans[kk]+=counts[i][kk]

for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

import random

D = int(input())
C = list(map(int, input().split()))  # (#cty,)
S = [list(map(int, input().split())) for _ in range(D)]  # (D, #cty)


class Scorer:

    def __init__(self, c, s):
        n_cty = len(c)
        self.c = c  # (#cty,)
        self.s = s  # (D, #cty)
        self.elapsed_time = {cty: 0 for cty in range(n_cty)}

        self.score = 0

    def update_score(self, d, cty):
        # update elapsed time
        for cty_ in self.elapsed_time:
            if cty_ == cty:
                self.elapsed_time[cty_] = 0
            else:
                self.elapsed_time[cty_] += 1

        cur_score = self.s[d][cty]
        for cty_ in self.elapsed_time:
            cur_score -= self.c[cty_] * self.elapsed_time[cty_]
        self.score += cur_score
        return self.score


T = None
best_score = -1
for _ in range(10000):
    scorer = Scorer(C, S)
    T_ = [random.randint(1, 26) for _ in range(D)]
    for d in range(D):
        cty = T_[d] - 1
        scorer.update_score(d, cty)
    if best_score <= scorer.score:
        best_score = scorer.score
        T = T_

for t in T:
    print(t)


### FIXED CODE ###

import random

D = int(input())
C = list(map(int, input().split()))  # (#cty,)
S = [list(map(int, input().split())) for _ in range(D)]  # (D, #cty)


class Scorer:

    def __init__(self, c, s):
        n_cty = len(c)
        self.c = c  # (#cty,)
        self.s = s  # (D, #cty)
        self.elapsed_time = {cty: 0 for cty in range(n_cty)}

        self.score = 0

    def update_score(self, d, cty):
        # update elapsed time
        for cty_ in self.elapsed_time:
            if cty_ == cty:
                self.elapsed_time[cty_] = 0
            else:
                self.elapsed_time[cty_] += 1

        cur_score = self.s[d][cty]
        for cty_ in self.elapsed_time:
            cur_score -= self.c[cty_] * self.elapsed_time[cty_]
        self.score += cur_score
        return self.score


N_REPLACE = 5
EPS = 0.5
ATT = 0.8

T = [random.randint(1, 26) for _ in range(D)]
best_score = -1
for _ in range(500):
    scorer = Scorer(C, S)

    T_ = T[:]

    # replace N elements
    for i in range(N_REPLACE):
        T_[random.randint(0, D - 1)] = random.randint(1, 26)

    for d in range(D):
        cty = T_[d] - 1
        scorer.update_score(d, cty)
    if best_score <= scorer.score:
        best_score = scorer.score
        T = T_
    elif random.random() < EPS:
        best_score = scorer.score
        T = T_
    EPS *= ATT

for t in T:
    print(t)
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0,1)]) # y,x,step
visited = [[False]*W for _ in range(H)]
visited[0][0] = True

while q:
    y,x,step = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - step)
        break
    visited[y][x] = True
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        if not(0<=y+dy<H and 0<=x+dx<W):
            continue
        if visited[y+dy][x+dx] or maze[y+dy][x+dx]=="#":
            continue
        q.append((y+dy, x+dx, step+1))
else:
    print(-1)

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0)])
dist = [[float('inf')]*W for _ in range(H)]
dist[0][0] = 1

while q:
    y,x = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - dist[y][x])
        break
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        nx,ny = x+dx, y+dy
        if not(0<=ny<H and 0<=nx<W):
            continue
        if maze[ny][nx]=="." and dist[ny][nx]==float('inf'):
            q.append((ny, nx))
            dist[ny][nx] = dist[y][x] + 1
else:
    print(-1)
### BUGGY CODE ###

s=input()


i=0
c=0
flag=0
while True:
	if i>len(s)-2: break
	if s[i]=="A":
		flag+=1
		i+=1
	elif flag and s[i:i+2]=="BC":
		s=s[:i-flag]+"BC"+"A"*flag+s[i+2:]
		c+=flag
		i+=2
	else:
		flag=0
		i+=1

print(c)



### FIXED CODE ###

s=input()


i=0
c=0
flag=0
while True:
	if i>len(s)-2: break
	if s[i]=="A":
		flag+=1
		i+=1
	elif flag and s[i:i+2]=="BC":
		c+=flag
		i+=2
	else:
		flag=0
		i+=1

print(c)
### BUGGY CODE ###

MOD = 10**9 + 7
s = input()[::-1]
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j + (10**i)*int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j + (10**i)*k) % 13] += dp[j]
				dpp[(j + (10**i)*k) % 13]  %= MOD
	dp = dpp
print(dp[5])

### FIXED CODE ###

MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])
### BUGGY CODE ###

# D - Knapsack Queries on a tree

import bisect

n = int(input())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, input().split())

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 15)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l) if u > 0 else 0
    if l >= w[u]:
        s = max(s, v[u] + (solve(parent, l - w[u]) if u > 0 else 0))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))


### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

n=int(input())
a=0
for i in range(n):
  a+=i
print(a)

### FIXED CODE ###

n=int(input())
a=(n-1)*n//2
print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


s = input()
K = int(input())
n = len(s)


def code(s):
    return ord(s)-97

def char(c):
    c = c % 26
    return chr(c+97)


ans = ""
for p in range(n):
    c = code(s[p])
    if c == 0:
        ans += "a"
        continue
    if 26-c > K:
        ans += s[p]
        continue
    ans += "a"
    K -= 26-c
ans = ans[:-1] + char(code(ans[-1])+K)

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


s = input()
K = int(input())
n = len(s)


def code(s):
    return ord(s)-97

def char(c):
    c = c % 26
    return chr(c+97)


# ans = ""
ans_list = []
for p in range(n):
    c = code(s[p])
    if c == 0:
        # ans += "a"
        ans_list.append("a")
        continue
    if 26-c > K:
        # ans += s[p]
        ans_list.append(s[p])
        continue
    # ans += "a"
    ans_list.append("a")
    K -= 26-c
ans = "".join(ans_list)
ans = ans[:-1] + char(code(ans[-1])+K)

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

import numpy as np
H, W = map(int, input().split())

path = []
for i in range(H):
    y = i+1
    row = list(map(int, input().split()))
    if i%2==0:
        for j, coin in enumerate(row):
               x = j+1
               path.append([y, x, coin])
    else:
        for j, coin in enumerate(row[::-1]):
               x = W-j
               path.append([y, x, coin])
path = np.array(path)

ans = []
for k in range(len(path)-1):
    c = path[k,2]
    if c%2==0:
        continue
    else:
        y, x = path[k, :2]
        ny, nx = path[k+1, :2]
        ans.append((y, x, ny, nx))
        path[k+1, 2] += 1

print(len(ans))
for a in ans:
    print(a[0], a[1], a[2], a[3])

### FIXED CODE ###

H, W = map(int, input().split())

path = []
for i in range(H):
    y = i+1
    row = list(map(int, input().split()))
    if i%2==0:
        for j, coin in enumerate(row):
               x = j+1
               path.append([y, x, coin])
    else:
        for j, coin in enumerate(row[::-1]):
               x = W-j
               path.append([y, x, coin])

ans = []
cnt = 0
for k in range(len(path)-1):
    c = path[k][2]
    if c%2==0:
        continue
    else:
        cnt += 1
        y, x = path[k][:2]
        ny, nx = path[k+1][:2]
        ans.append((y, x, ny, nx))
        path[k+1][2] += 1

print(cnt)
for a in ans:
    print(a[0], a[1], a[2], a[3])