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

# クラス1、2をP1、P2とする -> O(N)
# この後で累積和をとるために、先頭に0を加えておく
np_T = lambda x: [list(x) for x in zip(*x)]   # 転置
C, P = np_T(CP)
P1 = [0] + [p if c == 1 else 0 for p, c in zip(P, C)]
P2 = [0] + [p if c == 2 else 0 for p, c in zip(P, C)]
# P1、P2について累積和を求める　-> O(N)
# 求め方その1
for n in range(1, N + 1):  # P1の長さがN+1であることに注意
    P1[n] += P1[n - 1]
# 求め方その2
from itertools import accumulate
P2 = list(accumulate(P2))

# 累積和の差分として、解答を出力する -> 1回ごとO(1) × Q
for l, r in LR:
    print(P1[r] - P1[l-1], P2[r] - P2[l-1])

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
H = W = 1000

# 四隅に差分をセット（2次元が重なった差分は+1とする） -> O(N)
dat = [[0] * (W + 1) for _ in range(H + 1)]
for lx, ly, rx, ry in S:
    dat[ly][lx] += 1
    dat[ry][lx] -= 1
    dat[ly][rx] -= 1
    dat[ry][rx] += 1

# 二次元累積和をとることで、datは各座標の紙の枚数になる -> O(HW)
# （各次元ごとに累積和をとる）
for y in range(H + 1):
    for x in range(1, W + 1):
        dat[y][x] += dat[y][x - 1]
for x in range(W + 1):
    for y in range(1, H + 1):
        dat[y][x] += dat[y - 1][x]

# 紙の枚数ごとに集計することで、解答を得る -> O(HW)
ans = [0] * (N + 1)
for x in range(W + 1):
    for y in range(H + 1):
        ans[dat[y][x]] += 1

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

class BIT:
    def __init__(self, n):
        self.n = len(n) if isinstance(n, list) else n
        self.size = 1 << (self.n - 1).bit_length()
        if isinstance(n, list):  # nは1-indexedなリスト
            a = [0]
            for p in n: a.append(p + a[-1])
            a += [a[-1]] * (self.size - self.n)
            self.d = [a[p] - a[p - (p & -p)] for p in range(self.size + 1)]
        else:                    # nは大きさ
            self.d = [0] * (self.size + 1)

    def __repr__(self):
        p = self.size
        res = []
        while p > 0:
            res2 = []
            for r in range(p, self.size + 1, p * 2):
                l = r - (r & -r) + 1
                res2.append(f'[{l}, {r}]:{self.d[r]}')
            res.append(' '.join(res2))
            p >>= 1
        res.append(f'{[self.sum(p + 1) - self.sum(p) for p in range(self.size)]}')
        return '\n'.join(res)

    def add(self, p, x):  # O(log(n)), 点pにxを加算
        assert p > 0
        while p <= self.size:
            self.d[p] += x
            p += p & -p

    def get(self, p, default=None):     # O(log(n))
        assert p > 0
        return self.sum(p) - self.sum(p - 1) if 1 <= p <= self.n or default is None else default

    def sum(self, p):     # O(log(n)), 閉区間[1, p]の累積和
        assert p >= 0
        res = 0
        while p > 0:
            res += self.d[p]
            p -= p & -p
        return res

    def lower_bound(self, x):   # O(log(n)), x <= 閉区間[1, p]の累積和 となる最小のp
        if x <= 0: return 0
        p, r = 0, self.size
        while r > 0:
            if p + r <= self.n and self.d[p + r] < x:
                x -= self.d[p + r]
                p += r
            r >>= 1
        return p + 1

# Rの小さい順に並べる
# 各線分を(Li, Ri)として、新たな荷(Lk, Rk)に関して、
# Rkが前と同じでなく、Lkがそれまでの線分を通った数(*)
# の累積が求める数
# (*)は、各線分のLi+1を+1、Riを-1とした時の、点Lkまでの累積和
# ただし、L, R が1-indexedになっていることに注意
N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]

from collections import defaultdict
T = defaultdict(list)
for L, R in S:
    T[R].append(L)

bit = BIT(N)
ans = 0
for R in sorted(T.keys()):
    for L in T[R]:
        ans += bit.sum(L)
    for L in T[R]:
        bit.add(L + 1, 1)
        bit.add(R, -1)

print(ans)

# 転倒数を求める（必要ならXは座圧しておく）
def num_inversion(X):
    MAX = max(X)
    bit = BIT(MAX)
    res = 0
    for x in X:
        # 「xより左にあるxより大きい数」の個数を足す
        res += bit.sum(MAX) - bit.sum(x)
        bit.add(x, 1)
    return res

# BITのclass定義を貼り付ける
# 【競プロ】PyPy3で使える！Numpy代用ライブラリ より np_x_compress を貼り付ける

N, K = map(int, input().split())
A = np_x_compress(list(map(int, input().split())), offset=1)[0]
MOD = 10 ** 9 + 7
# リストAの位置rに対して、区間[l, r]の転倒数 <= K となる最小のlを、尺取法で求める
X = []
MAX = max(A)
bit = BIT(MAX)
num_inversion = 0
bit.add(A[0], 1)
l = r = 0
while True:
    # 得られた値をリストXに入れ、尺取位置を更新
    if num_inversion <= K:  # 転倒数がK以下ならば
        X.append(l)   # リストを更新
        r += 1        # 区間を伸ばす
        if r == N:
            break
        # A[r]より大きい数値が区間にいくつあるか をこれまでの転倒数に足す
        num_inversion += bit.sum(MAX) - bit.sum(A[r])
        bit.add(A[r], 1)
    else:             # 転倒数がKを超えていれば
        # A[l]より小さい数値が区間にいくつあるか をこれまでの転倒数から引く
        num_inversion -= bit.sum(A[l] - 1)
        bit.add(A[l], -1)
        l += 1        # 区間を縮める

dp = [1]                # 1-indexedでのnまでの答え
dp2 = [1]               # 答えの累積和
for r in range(1, N + 1):
    # dp[r] = dp[l - 1] + ... + dp[r - 1]
    # ただし l - 1 = X[r - 1] * 1-indexedに合わせるため
    if X[r - 1] - 1 >= 0:
        dp.append((dp2[r - 1] - dp2[X[r - 1] - 1]) % MOD)
    else:
        dp.append(dp2[r - 1] % MOD)
    dp2.append((dp[-1] + dp2[-1]) % MOD)
print(dp[-1])

class SegmentTree:
    # https://qiita.com/R_olldIce/items/32cbf5bc3ffb2f84a898
    def __init__(self, op, e, n):
        self.n = len(n) if isinstance(n, list) else n
        self.op = op
        self.e = e
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e for _ in range(2 * self.size)]
        if isinstance(n, list): self.d[self.size: self.size + self.n] = n
        [self._update(i) for i in reversed(range(1, self.size))]

    def __repr__(self):
        l, r = 1, 2
        res = []
        while r <= 2 * self.size:
            res.append(f'{self.d[l: r]}')
            l, r = r, r << 1
        return '\n'.join(res)

    def set(self, p, x):  # O(log n)
        p += self.size
        self.d[p] = x
        [self._update(p >> i) for i in range(1, self.log + 1)]

    def get(self, p):     # O(1)
        return self.d[p + self.size]

    def prod(self, l, r):  # [l, r)   O(log n)
        sml, smr = self.e, self.e
        l = max(l, 0) + self.size;
        r = min(r, self.n) + self.size;
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):   # O(1)
        return self.d[1]

    def _update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def max_right(self, l, f):   # f(prod(l,r)) == Trueとなる最大のr, O(log n)
        if l >= self.n: return self.n
        l = max(l, 0) + self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l <<= 1
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, f):   # f(prod(l,r)) == Trueとなる最小のl, O(log n)
        if r <= 0: return 0
        r = min(r, self.n) + self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r: break
        return 0

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

INF = 10 ** 16
from operator import add
seg = SegmentTree(max, -INF, W)  # 1点更新区間最大値取得
#seg = SegmentTree(min, INF, W)  # 1点更新区間最小値取得
#seg = SegmentTree(add, 0, W)  # 1点更新区間和取得
#seg = SegmentTree(二項演算子, 単位元, リスト)  # (リスト, 二項演算子, 単位元)はモノイド

dp = [-INF] * (W + 1)
dp[0] = 0
seg.set(0, 0)

for L, R, V in S:
    for w in range(L, R):
        dp[w] = max(dp[w], seg.prod(0, w - L + 1) + V)
    for w in range(R, W + 1):
        dp[w] = max(dp[w], seg.prod(w - R, w - L + 1) + V)
    seg = SegmentTree(max, -INF, dp)

print(dp[W] if dp[W] > 0 else -1)

class LazySegmentTree:
    def __init__(self, op, e, mapping, composition, id_, n):
        self._n = len(n) if isinstance(n, list) else n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id_
        self.log = (self._n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e for _ in range(2 * self.size)]
        self.lz = [id_ for _ in range(self.size)]
        if isinstance(n, list): self.d[self.size: self.size + self._n] = n
        [self._update(i) for i in reversed(range(1, self.size))]

    def __repr__(self):
        l, r = 1, 2
        res = []
        np_T = lambda x: [list(x) for x in zip(*x)]
        while r <= self.size:
            res.append(f'{np_T([self.d[l: r], self.lz[l: r]])}')
            l, r = r, r << 1
        res.append(f'{self.d[l: r]}')
        return '\n'.join(res)

    def set(self, p, x):  # O(log n)
        p += self.size
        [self._push(p >> i) for i in reversed(range(1, self.log + 1))]
        self.d[p] = x
        [self._update(p >> i) for i in range(1, self.log + 1)]

    def get(self, p):     # O(log n)
        p += self.size
        [self._push(p >> i) for i in reversed(range(1, self.log + 1))]
        return self.d[p]

    def prod(self, l, r):  # [l, r)   O(log n)
        if l == r: return self.e
        l += self.size
        r += self.size
        for i in reversed(range(1, self.log + 1)):
            if ((l >> i) << i) != l: self._push(l >> i)
            if ((r >> i) << i) != r: self._push((r - 1) >> i)
        sml, smr = self.e, self.e
        while (l < r):
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1;
            r >>= 1;
        return self.op(sml, smr)

    def all_prod(self):             # O(1)
        return self.d[1]

    def apply(self, p, f):          # O(log n)
        p += self.size;
        [self._push(p >> i) for i in reversed(range(1, self.log + 1))]
        self.d[p] = self.mapping(f, self.d[p]);
        [self._update(p >> i) for i in range(1, self.log + 1)]

    def apply_seg(self, l, r, f):   # O(log n)
        if l == r: return
        l += self.size;
        r += self.size;
        for i in reversed(range(1, self.log + 1)):
            if ((l >> i) << i) != l: self._push(l >> i)
            if ((r >> i) << i) != r: self._push((r - 1) >> i)
        l2, r2 = l, r
        while l < r:
            if l & 1:
                self._all_apply(l, f);
                l += 1
            if r & 1:
                r -= 1
                self._all_apply(r, f);
            l >>= 1;
            r >>= 1;
        l, r = l2, r2
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l: self._update(l >> i)
            if ((r >> i) << i) != r: self._update((r - 1) >> i)

    def max_right(self, l, f):   # f(prod(l,r)) == Trueとなる最大のr, O(log n)
        if l >= self._n: return self._n
        l = max(l, 0) + self.size
        for i in reversed(range(1, self.log + 1)):
            self._push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    self._push(l)
                    l <<= 1
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l: break
        return self._n

    def min_left(self, r, f):   # f(prod(l,r)) == Trueとなる最小のl, O(log n)
        if r <= 0: return 0
        r = min(r, self._n) + self.size
        for i in reversed(range(1, self.log + 1)):
            self._push((r - 1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    self._push(r)
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r: break
        return 0

    def _update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def _all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size: self.lz[k] = self.composition(f, self.lz[k])

    def _push(self, k):
        self._all_apply(2 * k, self.lz[k])
        self._all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.id

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

# モノイドdata=(X, op, e)、作用素モノイドlazy=(M, f: X×M → X, id_)
# seg = LazySegmentTree(op, e, f, f○g, id_, X)
# opが区間値取得演算、fが更新や加算などの区間変更演算に対応する
# fは区間計算できる必要がある。よってop=区間和の場合X=[(区間和, 区間長)]とする

INF = 10 ** 16
sum2 = lambda x, y: (x[0] + y[0], x[1] + y[1])  # (区間和, 区間長)同士を統合
# 区間加算演算
add = lambda f, x: f + x
add2 = lambda f, x: (x[0] + f * x[1], x[1])     # (区間和, 区間長)にfを加算
add_comp = lambda f, g: f + g
# 区間更新演算
update = lambda f, x: f if f < INF else x
update2 = lambda f, x: (f * x[1], x[1]) if f < INF else x  # 区間和計算して(値, 区間長)を更新
update_comp = lambda f, g: f if f < INF else g

# seg = LazySegmentTree(min, INF, update, update_comp, INF, W)  # 区間更新・区間最小値取得
seg = LazySegmentTree(max, -INF, update, update_comp, INF, W)  # 区間更新・区間最大値取得
# seg = LazySegmentTree(sum2, (0, 0), update2, update_comp, INF, [(0, 1)] * W)  # 区間更新・区間和取得
# seg = LazySegmentTree(min, INF, add, add_comp, 0, W)  # 区間加算・区間最小値取得
# seg = LazySegmentTree(max, -INF, add, add_comp, 0, W)  # 区間加算・区間最大値取得
# seg = LazySegmentTree(sum2, (0, 0), add2, add_comp, 0, [(0, 1)] * W)  # 区間加算・区間和取得

seg.apply_seg(0, W, 0)
for s in S:
    L, R = s
    height = seg.prod(L - 1, R) + 1
    seg.apply_seg(L - 1, R, height)
    print(height)

MOD = 998244353
def modsum2(x, y):
    x0, x1 = x >> 32, x % (1 << 32)
    y0, y1 = y >> 32, y % (1 << 32)
    return (((x0 + y0) % MOD) << 32) + x1 + y1
def affine2(f, x):
    f0, f1 = f >> 32, f % (1 << 32)
    x0, x1 = x >> 32, x % (1 << 32)
    return (((f0 * x0 + f1 * x1) % MOD) << 32) + x1
def affine_comp(f, g):
    f0, f1 = f >> 32, f % (1 << 32)
    g0, g1 = g >> 32, g % (1 << 32)
    return (((f0 * g0) % MOD) << 32) + (f0 * g1 + f1) % MOD

import sys
def input(): return sys.stdin.readline()[:-1]
N, Q = map(int, input().split())
a = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(Q)]
seg = LazySegmentTree(modsum2, 0, affine2, affine_comp, 1 << 32, [(a << 32) + 1 for a in a])
for t, l, r, *bc in S:
    if t == 0:
        b, c = bc
        seg.apply_seg(l, r, (b << 32) + c)
    else:
        print(seg.prod(l, r) >> 32)

# M = [(転倒数, 0の数, 1の数)] とする
inversion = lambda x, y: (x[0] + y[0] + x[2] * y[1], x[1] + y[1], x[2] + y[2])
not_ = lambda f, x: (x[1] * x[2] - x[0], x[2], x[1]) if f else x
not_comp = lambda f, g: f ^ g

import sys
def input(): return sys.stdin.readline()[:-1]
N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = [list(map(int, input().split())) for _ in range(Q)]

seg = LazySegmentTree(inversion, (0, 0, 0), not_, not_comp, False, [(0, 1 - a, a) for a in A])
for t, l, r in S:
    if t == 1:
        seg.apply_seg(l - 1, r, True)
    else:
        print(seg.prod(l - 1, r)[0])

N = int(input())

def parentheses_repr(bit):  # bitを括弧表現に変換
    res = []
    for n in range(N):
        if (bit >> n) & 1:  # bitテスト
            res.append(')')
        else:
            res.append('(')
    return ''.join(reversed(res))  # 逆順を元に戻す

for bit in range(2 ** N):
    nest = 0   # 括弧の深さ
    for n in range(N):  # 低位ビットを括弧列の右側（逆順）とする
        if (bit >> n) & 1:  # bitテスト
            nest += 1   # bit==1を')'として、深さを増やす
        else:
            nest -= 1   # bit==0を'('として、深さを減らす
        if nest < 0:    # 深さがマイナスになっらた条件不一致
            break
    if nest == 0:       # 最後に深さが0なら条件一致
        print(parentheses_repr(bit))

N, K, P = map(int, input().split())
A = list(map(int, input().split()))

N0 = N // 2

# 半分に分けられない場合を先に処理しておく
if N == 1:
    print(1 if A[0] <= P else 0)
    exit()

def bit_search(A):
    N = len(A)
    res = [[] for _ in range(N + 1)]
    for bit in range(2 ** N):
        p = 0
        k = 0
        for n in range(N):
            if (bit >> n) & 1:  # bitテスト
                p += A[n]
                k += 1
        if p <= P and k <= K:
            res[k].append(p)
    return res

# 半分全列挙
A0 = bit_search(A[:N0])
A1 = bit_search(A[N0:])
# 後半をソート
for a in A1:
    a.sort()

import bisect

ans = 0
# 前半から1つずつ結果を取り、個数合計がK・数値合計がP以下の後半部を二分探索
for k0, a0 in enumerate(A0):
    if K - k0 < len(A1):
        for p0 in a0:
            ans += bisect.bisect_right(A1[K - k0], P - p0)
print(ans)

N = int(input())
A = sorted(list(map(int, input().split())))    # ソート O(N logN)
Q = int(input())
B = [int(input()) for _ in range(Q)]

import bisect

for b in B:
    left = min(N - 1, bisect.bisect_left(A, b))    # 二分探索 O(logN)
    right = max(0, bisect.bisect_right(A, b) - 1)  # 二分探索 O(logN)
    cp = min(abs(b - A[left]), abs(b - A[right]))
    print(cp)

N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split())) + [L]

# チェック関数 O(N)
def check(n):      # スコアはn以上？をチェック
    k = 0          # kは、ようかんの固まりの数
    start = 0      # startは、現在のようかんの固まりの開始点
    for a in A:    # 貪欲法で固まりを切り出していく
        if a - start >= n:
            k += 1
            start = a
    return k > K   # K + 1以上の固まりが得られたかどうか

# 二分探索 O(log L) × チェック関数
low, high = 0, L + 1  # 半開区間 [low, high) をめいっぱい広くとる
while low + 1 < high: # low < mid < high とする
    mid = (low + high) // 2
    if check(mid):
        low = mid     # スコアはmid以上である -> 区間の下側を短縮
    else:
        high = mid    # スコアはmid未満である -> 区間の上側を短縮

print(low)

# 二分探索クラス（bisect利用、けむにくメソッド）
import bisect
class BinarySearch:
    # 半開区間[L, R)の広義単調増加check関数を、別に定義
    # solveは、check(x)==True を満たすxのもっとも右端を求める
    def __init__(self, L, R, check):
        self.L, self.R = L, R
        self.check = check
    def __len__(self):
        return self.R - self.L   # 区間長
    def __getitem__(self, i):
        return not self.check(self.L + i) # True -> 0, False -> 1
    def solve(self):
        return bisect.bisect_right(self, 0) + self.L - 1

# check関数は同一
def check(x):
    k = 0
    start = 0
    for a in A:
        if a - start >= x:
            k += 1
            start = a
    return k > K

N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split())) + [L]

bs = BinarySearch(0, L + 1, check)
print(bs.solve())

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

W_max = 50
B_max = 50 + W_max * (W_max + 1) // 2  # 途中状態でのB最大値

def mex(s):   # O(log len(s))、sはユニークなソート済みリスト
    if len(s) == 0 or s[0] > 0:  # 0は頻出なのでショートカット処理
        return 0
    def check(n):
        return n - 1 == s[n - 1] 
    low, high = 1, len(s) + 1
    while low + 1 < high:
        mid = (low + high) // 2
        if check(mid):
            low = mid
        else:
            high = mid
    return low

def _mex(s):   # O(len(s))だが定数倍が速い、sはユニークなソート済みリスト
    n = -1
    for n, x in enumerate(s):
        if n != x:
            return n
    return n + 1

grundy = [[0] * (B_max + 1) for _ in range(W_max + 1)]

for w in range(W_max + 1):
    for b in range(B_max + 1):
        if w == 0 and b <= 1 or b > B_max - w * (w + 1) // 2:  # Bの計算不要領域 
            continue
        s = set()
        if w >= 1:
            s.add(grundy[w - 1][b + w])
        if b >= 2:
            for k in range(1, b // 2 + 1):
                s.add(grundy[w][b - k])
        grundy[w][b] = mex(sorted(s))

ans = 0
for w, b in zip(W, B):
    ans ^= grundy[w][b]
print('First' if ans > 0 else 'Second')

N, K = map(int, input().split())
M = 10 ** 5
# 周期内の答えを前処理で求めておく
ans = [i for i in range(M)]
# 状態遷移 idx → next_index を求める
next_ = []
for i in range(M):
    x = ans[i]
    y = sum(map(int, list(str(x))))
    z = (x + y) % M
    next_.append(z)
# 開始地点からの遷移idx、
# ループ開始カウンタ:cnt_begin_loop、
# ループ合流カウンタ:cnt_merge_loopを求める
idx = [N]
cnt = [-1] * M
cnt[N] = 0
for c in range(1, M + 1):  # カウンタは1〜M
    next_idx = next_[idx[-1]]
    if cnt[next_idx] != -1:
        cnt_begin_loop = cnt[next_idx]
        cnt_merge_loop = c
        break
    cnt[next_idx] = c
    idx.append(next_idx)
# 周期性を意識してカウンタKの剰余を取る
if K >= cnt_begin_loop:
    K -= cnt_begin_loop
    K %= (cnt_merge_loop - cnt_begin_loop)
    K += cnt_begin_loop
# カウンタK→idx→答え
print(ans[idx[K]])

N, K = map(int, input().split())
M = 10 ** 5
T = K.bit_length()   # 2^T > N
next_ = []
# 1つ先の状態遷移を求める
next_.append([(m + sum(map(int, list(str(m))))) % M for m in range(M)])
# 2^t(<= N)個先の状態遷移を前計算する
for t in range(1, T):
    next_.append([next_[-1][next_[-1][m]] for m in range(M)])
# ダブリング
ans = N
for t in range(T):
    if (K >> t) & 1:
        ans = next_[t][ans]
print(ans)

N = int(input())
S = [list(map(int, input().split())) for _ in range(N - 1)]
# 無向グラフの典型入力
from collections import defaultdict
adj = defaultdict(list)
for a, b in S:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

import sys
sys.setrecursionlimit(10 ** 9)

def dfs(pos, seen, dist):   # dist（ここまでの距離）は問題固有のパラメータ
    seen[pos] = True

    # 行きがけ順の処理（最大距離と都市を求める）
    global max_dist, max_pos
    if max_dist < dist:
        max_dist = dist
        max_pos = pos

    # 次の位置を探索する
    for next_ in adj[pos]:
        if not seen[next_]:
            dfs(next_, seen, dist + 1)

    # 帰りがけ順の処理（この問題では記載なし）

max_dist = 0
max_pos = 0
dfs(0, [False] * N, 0)
dfs(max_pos, [False] * N, 0)
print(max_dist + 1)

N = int(input())
S = [list(map(int, input().split())) for _ in range(N - 1)]
# 無向グラフの典型入力
from collections import defaultdict
adj = defaultdict(list)
for a, b in S:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

def dfs(start):
    todo = [(0, start)]   # 初期探索場所をpush
    seen = [False] * N

    # 問題固有の前処理
    max_dist = 0
    max_pos = None

    while todo:
        dist, pos = todo.pop()   # LIFOでpop
        if seen[pos]:
            continue
        seen[pos] = True

        # 行きがけ順の処理（最大距離と都市を求める）
        if max_dist < dist:
            max_dist = dist
            max_pos = pos

        # 次の位置を探索する
        for next_ in adj[pos]:
            todo.append((dist + 1, next_))
    return max_dist, max_pos

_, max_pos = dfs(0)
max_dist, _ = dfs(max_pos)
print(max_dist + 1)

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

# 無向グラフの典型入力
from collections import defaultdict
adj = defaultdict(list)
for a, b in S:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

def dfs(pos):
    todo = [(0, ~pos), (0, pos)]  # 初期探索場所をpush
    seen = [False] * N
    finished = [False] * N

    # 問題固有の前処理
    max_dist = 0
    max_pos = None

    while todo:
        dist, pos = todo.pop()    # LIFOでpop
        if pos >= 0: 
            if finished[pos]:
                continue
            seen[pos] = True
            # 行きがけ順の処理（最大距離と都市を求める）
            if max_dist < dist:
                max_dist = dist
                max_pos = pos
            # 次の位置を探索する
            for next_ in adj[pos]:
                if seen[next_]:
                    continue
                todo.append((dist + 1, ~next_)) # 帰りがけはビット反転
                todo.append((dist + 1, next_))
        else:
            pos = ~pos   # ビット反転を戻す
            if finished[pos]:
                continue
            finished[pos] = True
            # 帰りがけ順の処理（この問題では記載なし）
    return max_dist, max_pos

_, max_pos = dfs(0)
max_dist, _ = dfs(max_pos)
print(max_dist + 1)

import sys
def input(): return sys.stdin.readline()[:-1]
N = int(input())
P = list(map(int, input().split()))
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]

# 親リストPを使った無向グラフの典型入力
from collections import defaultdict
adj = defaultdict(list)
for c, p in enumerate(P):
    adj[p-1].append(c+1)
    adj[c+1].append(p-1)

INF = 10 ** 18
# オイラーツアーと深さを算出
def dfs(pos):
    todo = [(0, ~pos), (0, pos)]
    in_ = [INF] * N
    out = [INF] * N
    depth = [INF] * N
    count = 0
    while todo:
        dist, pos = todo.pop()
        if pos >= 0: 
            if out[pos] < INF:
                continue
            in_[pos] = count
            count += 1
            depth[pos] = dist
            for next_ in adj[pos]:
                if in_[next_] < INF:
                    continue
                todo.append((dist, ~next_))
                todo.append((dist + 1, next_))
        else:
            pos = ~pos
            if out[pos] < INF:
                continue
            out[pos] = count
            count += 1
    return in_, out, depth

in_, out, depth = dfs(0)

# 深さごとにin_の値を昇順に保持
depth_in = defaultdict(list)
for n in range(N):
    depth_in[depth[n]].append(in_[n])
for d in depth_in.keys():
    depth_in[d].sort()
# クエリーを答える
import bisect
for U, D in query:
    u_in = in_[U - 1]
    u_out = out[U - 1]
    ans = bisect.bisect_left(depth_in[D], u_out) - bisect.bisect_left(depth_in[D], u_in)
    print(ans)

N = int(input())
S = [list(map(int, input().split())) for _ in range(N - 1)]
# 無向グラフの典型入力
from collections import defaultdict
adj = defaultdict(list)
for a, b in S:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)

from collections import deque

def bfs(start):
    todo = deque()
    todo.append((0, start))   # 初期探索場所をpush
    seen = [False] * N

    # 問題固有の前処理
    max_dist = 0
    max_pos = None

    while todo:
        dist, pos = todo.popleft()   # FIFOでpop
        if seen[pos]:
            continue
        seen[pos] = True

        # 行きがけ順の処理（最大距離と都市を求める）
        if max_dist < dist:
            max_dist = dist
            max_pos = pos

        # 次の位置を探索する
        for next_ in adj[pos]:
            todo.append((dist + 1, next_))
    return max_dist, max_pos

_, max_pos = bfs(0)
max_dist, _ = bfs(max_pos)
print(max_dist + 1)

N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 16

# ワーシャルフロイド法の初期設定としての、ノード間のコスト設定
dist = [INF] * N * N
def _(i, j): return i * N + j  # 1次元化簡易記述（基本編参照）
for a, b, c in S:
    dist[_(a-1, b-1)] = c  # この問題は一方通行であることに注意
#   dist[b-1][a-1] = c
for n in range(N):
    dist[_(n, n)] = 0

ans = 0
# ワーシャルフロイド法
for k in range(N):   # 中継ノード
    for s in range(N):
        for t in range(N):
            dist[_(s, t)] = min(dist[_(s, t)], dist[_(s, k)] + dist[_(k, t)])  # 中継ノードを介したコスト改善
            if dist[_(s, t)] < INF:   # 全てのs,t,kでの総和
                ans += dist[_(s, t)]
print(ans)

N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
# 距離付き無向グラフの典型入力
from collections import defaultdict
adj = defaultdict(list)
for a, b, c in S:
    adj[a-1].append((b-1, c))
    adj[b-1].append((a-1, c))

INF = float('inf')
import heapq

def dijkstra(start):
    dist = [INF] * N
    dist[start] = 0
    h = []
    heapq.heappush(h, (0, start))
    while h:
        d, pos = heapq.heappop(h)  # 最短距離の頂点
        if d != dist[pos]:
            continue
        for next_, cost in adj[pos]:   # 隣接候補
            next_d = d + cost
            if next_d < dist[next_]:
                dist[next_] = next_d   # 最短距離を更新
                heapq.heappush(h, (next_d, next_))   # 最短距離をヒープキューで管理
    return dist

d1 = dijkstra(0)    # 街1から各街への距離
d2 = dijkstra(N-1)  # 街Nから各街への距離

for k in range(N):
    print(d1[k] + d2[k])