提出 #76970826

---

ソースコード 拡げる

##pypyですよー
#iiiiiiiiiiiiiiiiiiiiiiiiiiiiyasassa
##kusawww
##kusawww
##kusawww
##kusawww
##kusawww
import sys
sys.setrecursionlimit(10**5)##再帰対策
import math
import random
import itertools
import platform
import collections
import heapq
import bisect
from bisect import bisect_right
from collections import deque
from heapq import heappush, heappop, nlargest, nsmallest
#from heapq import *だと多分実行環境のせいでREでるんだけど。うざい
from functools import reduce
from itertools import zip_longest, accumulate
import operator
import copy
from collections import Counter
import sys
import numpy as np

input = lambda: sys.stdin.readline().rstrip()
"""
input = sys.stdin.readlineだとelseでinputにはないのにこいつに"\n"が含まれるから反応しちゃう。
(else:)で改行のせいで読み込まれて処理が行われる
なのでこうして、改行しないようにする
"""
###############################n
#numpyがpypyだと遅いので脳筋で
"""
本来npは.だがnumpy使えない場合
_で代用

# 基本プロパティ
_is_array_like = lambda a: isinstance(a, tuple) or isinstance(a, list)
np_shape = lambda a: (len(a), *np_shape(a[0])) if _is_array_like(a) else ()
math_prod = lambda a: reduce(operator.mul, a, 1)
np_size = lambda a: math_prod(np_shape(a))
np_ndim = lambda a: len(np_shape(a))
np_strides = lambda a: tuple(accumulate((1, *(np_shape(a)[:0:-1])), operator.mul))[::-1]  # 要素のサイズは1
# 変形
np_flatten = lambda a: np_flatten([a for a in a for a in a]) if np_ndim(a) > 1 else a if np_ndim(a) == 1 else [a]
def _np_shape_complement(shape, size):   # -1を含むshapeをsizeをもとに補完する
    shape0 = shape[0] if shape[0] > 0 else abs(size // math_prod(shape))
    return (shape0,) if len(shape) == 1 else (shape0, *_np_shape_complement(shape[1:], size // shape0))
_np_reshape = lambda a, newshape: [_np_reshape(a[n: n + len(a) // newshape[0]], newshape[1:]) for n in range(0, len(a), len(a) // newshape[0])] if len(newshape) > 1 else a
np_reshape = lambda a, newshape: _np_reshape(np_flatten(a), _np_shape_complement(newshape, np_size(a)))
_np_tile = lambda a, reps2: _np_tile([[copy.deepcopy(a[n + m % reps2[-1][0]]) for m in range(math_prod(reps2[-1]))] for n in range(0, len(a), reps2[-1][0])], reps2[:-1]) if len(reps2) > 0 else a
np_tile = lambda a, reps: _np_tile(np_flatten(a), list(zip_longest(np_shape(a)[::-1], reps[::-1], fillvalue=1))[::-1])[0]
np_broadcast_to = lambda a, shape: np_tile(a, [n // m for m, n in zip_longest(np_shape(a)[::-1], shape[::-1], fillvalue=1)][::-1])
np_broadcast_shapes = lambda *args: tuple(map(max, *[(1,) * (max([len(shape) for shape in args]) - len(shape)) + shape for shape in args]))
np_broadcast_arrays = lambda *args: [np_broadcast_to(a, np_broadcast_shapes(*map(np_shape, args))) for a in args]
# スライス
_np_slice = lambda x, k: x[k] if not _is_array_like(k) else [_np_slice(x, k[1:]) for x in x][k[0]] if len(k) > 1 else x[k[0]] # sはsliceのリスト
##kusawwwすぎる
##一次元
# 最大値のインデックス
np_argmax = lambda x: max([(x, i) for i, x in enumerate(x)])[-1]
# 最小値のインデックス
np_argmin = lambda x: min([(x, i) for i, x in enumerate(x)])[-1]
# ソート順のインデックス
np_argsort = lambda x: [x[-1] for x in sorted([(x, i) for i, x in enumerate(x)])]

##二次元
# 生成
np_zeros = lambda shape: np_reshape([0] * math_prod(shape), shape)  # 任意のn(>= 1)次元に適用可能
np_ones = lambda shape: np_reshape([1] * math_prod(shape), shape)  # 任意のn(>= 1)次元に適用可能
np_identity = lambda n: [[1 if i == j else 0 for j in range(n)] for i in range(n)]   # 2次元のみ
np_arange = lambda *args: list(range(*args))   # 1次元のみ
# 転置・反転・回転　　　# 2次元のみ
np_T = lambda x: [list(x) for x in zip(*x)]
np_flip = lambda x, axis=None: np_flip(np_flip(x, axis=0), axis=1) if axis == None else [x for x in reversed(x)] if axis == 0 else [list(reversed(x)) for x in x]
np_rot90 = lambda x, k=1: np_flip(np_T(x), axis=0) if k % 4 == 1 else np_rot90(np_rot90(x, k=(k + 3) % 4))
# 単項演算(opにはoperatorを入れる)  
# ※ axisは2次元のみ、axis指定なしは任意のn(>= 1)次元に適用可能。
#   ただし、1次元は標準の組み込み関数で代用可能
_np_unary = lambda op, x, axis=None: [op(x) for x in zip(*x)] if axis == 0 else [op(x) for x in x] if axis == 1 or axis == -1 else op(np_flatten(x))
np_sum = lambda x, axis=None: _np_unary(sum, x, axis)
np_max = lambda x, axis=None: _np_unary(max, x, axis)
np_min = lambda x, axis=None: _np_unary(min, x, axis)
np_all = lambda x, axis=None: _np_unary(lambda x: reduce(operator.and_, x) != 0, x, axis)
np_any = lambda x, axis=None: _np_unary(lambda x: reduce(operator.or_, x) != 0, x, axis)
# 二項演算(opにはoperatorを入れる)  ※ 任意のn(>= 1)次元に適用可能
_np_binomial = lambda op, x, y: [_np_binomial(op, x, y) if _is_array_like(x) else op(x, y) for x, y in zip(*np_broadcast_arrays(x, y))]   # ブロードキャスト可
_np_binomial2 = lambda op, x, y: [_np_binomial2(op, x, y) if _is_array_like(x) else op(x, y) for x, y in zip(x, y)]   # ブロードキャスト不可だが高速
np_add = lambda x, y: _np_binomial(operator.add, x, y)
np_sub = lambda x, y: _np_binomial(operator.sub, x, y)
np_mul = lambda x, y: _np_binomial(operator.mul, x, y)
np_floordiv = lambda x, y: _np_binomial(operator.floordiv, x, y)
np_mod = lambda x, y: _np_binomial(operator.mod, x, y)
np_eq = lambda x, y: _np_binomial(operator.eq, x, y)
np_ne = lambda x, y: _np_binomial(operator.ne, x, y)
np_lt = lambda x, y: _np_binomial(operator.lt, x, y)
np_le = lambda x, y: _np_binomial(operator.le, x, y)
np_gt = lambda x, y: _np_binomial(operator.gt, x, y)
np_ge = lambda x, y: _np_binomial(operator.ge, x, y)
np_array_equal = lambda x, y: np_shape(x) == np_shape(y) and np_all(_np_binomial2(operator.eq, x, y))
# インデックス
np_ravel_multi_index = lambda multi_index, shape: np_sum(np_mul(np_T(multi_index), np_strides(np_zeros(shape))), axis=1)
_np_unravel_index = lambda indices, strides:  indices[:-1] if len(strides) == 0 else _np_unravel_index(indices[:-1] + [indices[-1] // strides[0], indices[-1] % strides[0]], strides[1:])
np_unravel_index = lambda indices, shape: np_T([_np_unravel_index([x], np_strides(np_zeros(shape))) for x in indices])
np_nonzero = lambda x: tuple(np_unravel_index([i for i, x in enumerate(np_flatten(x)) if x != 0], np_shape(x)))
# 行列積　　　※ 2次元のみ
from itertools import product
np_matmul = lambda x, y: np_reshape([sum(map(operator.mul, x, y)) for x, y in product(x, np_T(y))], (len(x), -1))


###np.zeros のようにするため、ちょっと処理遅くなるので注意
class np:
    @classmethod
    def array(cls, a): return ndarray(a)
    @classmethod
    def zeros(cls, shape): return cls.array(np_zeros(shape))
    @classmethod
    def ones(cls, shape): return cls.array(np_ones(shape))
    @classmethod
    def identity(cls, n): return cls.array(np_identity(n))
    @classmethod
    def arange(cls, *args): return cls.array(np_arange(*args))

class ndarray(list):
    def _rc(self, a): return ndarray(a) if _is_array_like(a) else a
    @property
    def shape(self): return np_shape(self)
    @property
    def size(self): return np_size(self)
    @property
    def ndim(self): return np_ndim(self)
    @property
    def T(self): return ndarray(np_T(self))
    def flatten(self): return ndarray(np_flatten(self))
    def reshape(self, *newshape): return ndarray(np_reshape(self, newshape))
    def sum(self, axis=None): return np_sum(self, axis) if axis is None else ndarray(np_sum(self, axis))
    def max(self, axis=None): return np_max(self, axis) if axis is None else ndarray(np_max(self, axis))
    def min(self, axis=None): return np_min(self, axis) if axis is None else ndarray(np_min(self, axis))
    def __add__(self, other): return ndarray(np_add(self, other))
    def __sub__(self, other): return ndarray(np_sub(self, other))
    def __mul__(self, other): return ndarray(np_mul(self, other))
    def __floordiv__(self, other): return ndarray(np_floordiv(self, other))
    def __mod__(self, other): return ndarray(np_mod(self, other))
    def __radd__(self, other): return ndarray(np_add(other, self))
    def __rsub__(self, other): return ndarray(np_sub(other, self))
    def __rmul__(self, other): return ndarray(np_mul(other, self))
    def __rfloordiv__(self, other): return ndarray(np_floordiv(other, self))
    def __rmod__(self, other): return ndarray(np_mod(other, self))
    def __matmul__(self, other): return ndarray(np_matmul(self, other))
    def __getitem__(self, k): return self._rc(_np_slice(list(self), k))

"""
#####################################
#####################################
#####################################    
#####################################
YN = lambda x: print(("No", "Yes")[x])  ### YN(a == b)

INF = 10**18
II = lambda: int(input())     ##II() にする必要あり!!!!!!!!!!!!!!
IMI = lambda: map(int, input().split())

SI = lambda: input()              # 文字列1行
SMI = lambda: input().split() 
    # 文字列リスト banana manngo gorira -->a,b,c=SMI -->a==banana.... 

HITOTU = lambda: list(input())       # 1文字ずつリスト化　abcd -> a b c d
LII = lambda: list(map(int, input().split()))
LSI = lambda: list(map(str, input().split()))## a b c -> [a,b,c]  空白区切っているので
INF = 10**18
PL = lambda a: print(*a) ##a = [1, 2, 3, 4, 5]
                         ##PL(a)                 --> 1 2 3 4 5

dame = lambda: print("-1")
PIF = lambda c, *a: c and print(*a) # PIF(x>0,"a")


#####################################
#####################################
#####################################
#####################################
# ==========================
# 数学
# ==========================

def is_prime(n: int) -> bool:
    """素数判定"""
    if n <= 1:
        return False

    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1

    return True


def eratosthenes(n: int) -> list[int]:
    """n以下の素数列挙"""
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if prime[i]:
            for j in range(i * i, n + 1, i):
                prime[j] = False

    return [i for i in range(n + 1) if prime[i]]


def calc_divisors(n: int) -> list[int]:
    """約数列挙"""
    res = []

    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            res.append(i)

            if i != n // i:
                res.append(n // i)

    return sorted(res)


def factorization(n: int):
    """素因数分解"""
    res = []

    d = 2

    while d * d <= n:
        cnt = 0

        while n % d == 0:
            cnt += 1
            n //= d

        if cnt:
            res.append((d, cnt))

        d += 1

    if n > 1:
        res.append((n, 1))

    return res


def factorization_plural(arr):
    """複数素因数分解"""
    return [factorization(x) for x in arr]


def simple_sigma(n):
    """1~nの和"""
    return n * (n + 1) // 2


def comb(n, r):
    """nCr"""
    from math import comb
    return comb(n, r)

def base(n, s, f):
    # n: s進数（文字列,整数）
    # s: 元の進数
    # f: 変換後の進数

    digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" #35進数まで行けるはず

    # 10進数へ変換
    x = int(str(n), s)

    # 0は特別です
    if x == 0:
        return "0"

    # f進数へ変換
    res = ""
    while x > 0:
        res = digits[x % f] + res
        x //= f

    return res


def mod_add(a, b, mod):
    return (a + b) % mod


def mod_sub(a, b, mod):
    return (a - b) % mod


def mod_mul(a, b, mod):
    return (a * b) % mod


def mod_div(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


class ModInt:
    def __init__(self, value, mod=998244353):
        self.mod = mod
        self.value = value % mod

    def __add__(self, other):
        if isinstance(other, ModInt):
            other = other.value
        return ModInt(self.value + other, self.mod)

    def __sub__(self, other):
        if isinstance(other, ModInt):
            other = other.value
        return ModInt(self.value - other, self.mod)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            other = other.value
        return ModInt(self.value * other, self.mod)

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            other = other.value
        return ModInt(
            self.value * pow(other, self.mod - 2, self.mod),
            self.mod
        )

    def __pow__(self, n):
        return ModInt(pow(self.value, n, self.mod), self.mod)

    def __repr__(self):
        return str(self.value)

    def __int__(self):
        return self.value

def sigma(A):
    return sum(A)


def prod(A):##総積
    ans = 1

    for x in A:
        ans *= x

    return ans


def average(A):
    return sum(A) / len(A)

# ==========================
# bit
# ==========================

def bitcount(x):
    return bin(x).count("1")
"""
x を2進数にして
1の数を数える"""


def kth_bit(x, k):
    return (x >> k) & 1

"""
x を右に k 回ずらす
最下位ビットだけ見る"""
def bit_on(x, k):
    return x | (1 << k)
"""k番目を 1 にする"""

def bit_off(x, k):
    return x & ~(1 << k)
"""今度は0にする"""

# ==========================
# coordinate
# ==========================

def inside(x, y, h, w):
    return 0 <= x < h and 0 <= y < w
"""マスの範囲チェック"""

def pos2id(x, y, w):
    return x * w + y
"""2D → 1D"""

def id2pos(id, w):
    return id // w, id % w
"""1D 2D"""
# ==========================
# Stack (入口入れて、入口から)
# ==========================

class Stack:
    def __init__(self):
        self.data = []

    def push(self, x):
        """要素追加"""
        self.data.append(x)

    def pop(self):
        """一番上を取り出して削除"""
        return self.data.pop()

    def top(self):
        """一番上を見る"""
        return self.data[-1]

    def empty(self):
        """空か判定"""
        return len(self.data) == 0

    def size(self):
        """要素数"""
        return len(self.data)

    def clear(self):
        """全削除"""
        self.data.clear()

    def contains(self, x):
        """xが存在するか"""
        return x in self.data

    def count(self, x):
        """xの個数"""
        return self.data.count(x)

    def freq(self):
        """各値の出現回数"""
        return Counter(self.data)

    def to_list(self):
        """リスト化"""
        return self.data[:]
    

    def copy(self):
        """kopiru"""
        new_stack = Stack()
        new_stack.data = self.data[:]
        return new_stack

    def reverse(self):
        self.data.reverse()
    
    def pop_all(self):
        """全部はきだすー＞epmptyになる"""
        res = self.data[:]
        self.data.clear()
        return res

# ==========================
# Queue (入口に入れ、出口から出てくる),dequeのクラス版(両端)
# ==========================
class Deque:
    def __init__(self):
        """初期化"""
        self.data = deque()

    def push_back(self, x):
        """末尾に追加"""
        self.data.append(x)

    def append(self, x):
        """末尾に追加"""
        self.data.append(x)

    def push_front(self, x):
        """先頭に追加"""
        self.data.appendleft(x)

    def pop_back(self):
        """末尾を取り出して削除"""
        return self.data.pop()

    def pop_front(self):
        """先頭を取り出して削除"""
        return self.data.popleft()

    def front(self):
        """先頭を見る"""
        return self.data[0]

    def back(self):
        """末尾を見る"""
        return self.data[-1]

    def get(self, i):
        """i番目の要素を見る"""
        return self.data[i]

    def set(self, i, x):
        """i番目の要素をxに変更"""
        self.data[i] = x

    def empty(self):
        """空か判定"""
        return len(self.data) == 0

    def size(self):
        """要素数"""
        return len(self.data)

    def clear(self):
        """全削除"""
        self.data.clear()

    def reverse(self):
        """反転"""
        self.data.reverse()

    def rotate(self, k):
        """右にk回転（負なら左回転）"""
        self.data.rotate(k)

    def extend(self, lst):
        """末尾にリストを追加"""
        self.data.extend(lst)

    def extend_left(self, lst):
        """先頭にリストを追加"""
        self.data.extendleft(lst)

    def remove(self, x):
        """最初に見つかったxを削除"""
        self.data.remove(x)

    def contains(self, x):
        """xが存在するか"""
        return x in self.data

    def count(self, x):
        """xの個数"""
        return self.data.count(x)

    def freq(self):
        """各値の出現回数"""
        return Counter(self.data)

    def to_list(self):
        """リスト化"""
        return list(self.data)

    def copy(self):
        """複製"""
        d = Deque()
        d.data = self.data.copy()
        return d

    def pop_all(self):
        """全部取り出して空にする"""
        res = list(self.data)
        self.data.clear()
        return res

    def __getitem__(self, i):#添え字可能
        return self.data[i]
    
class Queue:
    def __init__(self):
        self.data = deque()

    def push(self, x):
        """末尾に追加"""
        self.data.append(x)

    def pop(self):
        """先頭を取り出して削除"""
        return self.data.popleft()

    def front(self):
        """先頭を見る"""
        return self.data[0]

    def back(self):
        """末尾を見る"""
        return self.data[-1]

    def empty(self):
        """空か判定"""
        return len(self.data) == 0 
    """
    if q.empty():
    print("空！")
    """

    def size(self):
        """要素数"""
        return len(self.data)
    """
print(q.size())
"""
    def clear(self):
        """全削除"""
        self.data.clear()

    def contains(self, x):
        """xが存在するか"""
        return x in self.data

    def count(self, x):
        """xの個数"""
        return self.data.count(x)

    def freq(self):
        """各値の出現回数"""
        return Counter(self.data)
    """
    print(q.freq())->Counter({3: 2, 1: 1, 4: 1})  頻度カウンたー"""

    def to_list(self):
        """リスト化"""
        return list(self.data)
    
    """
    lst = q.to_list()
print(lst)"""


    def copy(self):
         return Queue.from_list(self.to_list())
    
  
    def from_list(cls, lst):
        q = cls()
        q.data = deque(lst)
        return q
    def reverse(self):
        self.data.reverse()

    def pop_all(self):
        """全部はきだすー＞epmptyになる"""
        res = list(self.data)
        self.data.clear()
        return res

# ==========================
# PriorityQueue (
# ==========================

class PQ:#最小値
    def __init__(self):
        self.data = []

    def push(self, x):
        """要素追加"""
        heappush(self.data, x)

    def pop(self):
        """最小値を取り出して削除"""
        return heappop(self.data)

    def top(self):
        """最小値を見る"""
        return self.data[0]

    def empty(self):
        """空か判定"""
        return len(self.data) == 0

    def size(self):
        """要素数"""
        return len(self.data)

    def clear(self):
        """全削除"""
        self.data.clear()

    def contains(self, x):
        """xが存在するか"""
        return x in self.data

    def count(self, x):
        """xの個数"""
        return self.data.count(x)

    def freq(self):
        """各値の出現回数"""
        return Counter(self.data)

    def to_list(self):
        """小さい順のリストを返す"""
        return sorted(self.data)
    
    def copy(self):
        """複製して返す"""
        new = PQ()
        new.data = self.data.copy()
        return new
    
    def pop_all(self):
        """全部はきだす(oeeeeeeeeeeeeeeeeeeeeeeee)ー＞epmptyになる"""
        res = []
        while self.data:
            res.append(heappop(self.data))
        return res
    

    def nsmallest(self, n):
        """小さい順にn個取得（削除しない）"""
        return nsmallest(n, self.data)

    def nlargest(self, n):
        """大きい順にn個取得（削除しない）"""
        return nlargest(n, self.data)

"""
pq = PQ()

pq.push(10)
pq.push(3)
pq.push(7)
pq.push(3)

print(pq.top())      # 3
print(pq.count(3))   # 2
print(pq.size())     # 4
print(pq.freq())     # Counter({3:2,10:1,7:1})

print(pq.pop())      # 3
print(pq.pop())      # 3
print(pq.pop())      # 7
print(pq.pop())      # 10
"""
##heapのみの時
###heapq.heappush(h, 5)
##heapq.heappush(h, 1)
##heapq.heappush(h, 10)





class MaxPQ:#最大値
    def __init__(self):
        self.data = []

    def push(self, x):
        """要素追加（最大ヒープ）"""
        heappush(self.data, -x)

    def pop(self):
        """最大値を取り出して削除"""
        return -heappop(self.data)

    def top(self):
        """最大値を見る"""
        return -self.data[0]

    def empty(self):
        """空か判定"""
        return len(self.data) == 0

    def size(self):
        """要素数"""
        return len(self.data)

    def clear(self):
        """全削除"""
        self.data.clear()

    def contains(self, x):
        """xが存在するか"""
        return -x in self.data

    def count(self, x):
        """xの個数"""
        return self.data.count(-x)

    def freq(self):
        """各値の出現回数"""
        return Counter(-x for x in self.data)

    def to_list(self):
        """大きい順のリストを返す"""
        return sorted((-x for x in self.data), reverse=True)
    
    def copy(self):
        """同じ内容のMaxPQを複製して返す"""
        new = MaxPQ()
        new.data = self.data.copy()
        return new
    

    def pop_all(self):
        """全部はきだす(orororororor)ー＞epmptyになる"""
        res = []
        while self.data:
            res.append(-heappop(self.data))
        return res
    
    def nlargest(self, n):
        """大きい順にn個取得（削除しない）"""
        return [-x for x in nsmallest(n, self.data)]

    def nsmallest(self, n):
        """小さい順にn個取得（削除しない）"""
        return [-x for x in nlargest(n, self.data)]
# ==========================
# マルチリスト
# ==========================

class MultiSet:
    def __init__(self):
        self.cnt = Counter()

    def add(self, x):
        self.cnt[x] += 1

    def remove(self, x):
        if self.cnt[x]:
            self.cnt[x] -= 1
            if self.cnt[x] == 0:
                del self.cnt[x]

    def count(self, x):
        return self.cnt[x]

    def contains(self, x):
        return x in self.cnt

    def size(self):
        return sum(self.cnt.values())
"""
ms.add(5)
ms.add(5)

ms.count(5)
-> 2
"""
# ==========================
# 累積和
# ==========================
def ruiseki1(arr):
    N = len(arr)
    S = [0] * (N + 1)  # S[0] = 0 として扱う
    for i in range(N):
        S[i + 1] = S[i] + arr[i]
    return S


def ruiseki2(grid):
    H, W = len(grid), len(grid[0])
    S = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        for j in range(W):
            S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + grid[i][j]
    return S##https://qiita.com/Midori_M/items/5475061656f562dd675c引用

# ==========================
# min max
# ==========================

def argmin(A):  ##最小値の位置 intをかえす
    return min(range(len(A)), key=lambda i: A[i])


def argmax(A):
    return max(range(len(A)), key=lambda i: A[i])



# ==========================
# ランレングス圧縮
# ==========================
"""
    aaabbccccー＞
    [('a',3), ('b',2), ('c',4)]
    """
def rle(s):
    if not s:
        return []

    res = []

    cur = s[0]
    cnt = 1

    for c in s[1:]:
        if c == cur:
            cnt += 1
        else:
            res.append((cur, cnt))
            cur = c
            cnt = 1

    res.append((cur, cnt))

    return res


# ==========================
# インデックスに変換
# ==========================

def compress(A):
    S = sorted(set(A))

    mp = {x:i for i,x in enumerate(S)}

    return [mp[x] for x in A]


"""
A = [100, 500, 100, 1000]

print(compress(A))->[0, 1, 0, 2]
"""

# ==========================
# グラフ
# ==========================

def make_graph(n, edges):#無向用
    G = [[] for _ in range(n)]

    for u, v in edges:
        G[u].append(v)
        G[v].append(u)

    return G
# ==========================
# 配列
# ==========================

def list1di(n, default=0):
    return [default] * n


def list2di(h, w, default=0):
    return [[default] * w for _ in range(h)]


def list3di(x, y, z, default=0):
    return [[[default] * z for _ in range(y)] for _ in range(x)]
"""
A = crar1(5)
print(A)->[0, 0, 0, 0, 0]

A = crar1(4, -1)
print(A)->[-1, -1, -1, -1]
"""





# ==========================
# list,文字列
# ==========================

def flatten(A):
    """2次元→1次元"""
    return [x for row in A for x in row]


def unique(A):
    """重複削除(順序維持)"""
    return list(dict.fromkeys(A))


def chunks(A, k):
    """k個ずつ分割"""
    return [A[i:i+k] for i in range(0, len(A), k)]



def is_palindrome(s):
    """回文か"""
    return s == s[::-1]###print(is_palindrome("level")) -> True



def reverse_str(s):
    return s[::-1]


def rotate_str(s,k):
    """ｋ回分左に"""
    k %= len(s)
    return s[k:] + s[:k]##rotate_str("abcdef",2)->cdefab
# ==========================
# ChMin ChMax
# ==========================

class ChangeMin:
    def __init__(self, x):
        self.x = x

    def set(self, v):
        self.x = min(self.x, v)

    def val(self):
        return self.x


class ChangeMax:
    def __init__(self, x):
        self.x = x

    def set(self, v):
        self.x = max(self.x, v)

    def val(self):
        return self.x
####以下のように====
"""
A = [7, 2, 9, 1, 5]

mn = ChangeMin(float("inf"))

for x in A:
    mn.set(x)

print(mn.val())           -> 1
"""

# ==========================
# alpha,num
# ==========================
LOWER = "abcdefghijklmnopqrstuvwxyz"
UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
DIGIT = "0123456789"

ALPHA = LOWER + UPPER
ALNUM = ALPHA + DIGIT


# ==========================
# 距離
# ==========================
def euclid(x1, y1, x2, y2):
    """ユークリッド距離"""
    return ((x1-x2)**2 + (y1-y2)**2) ** 0.5


def euclid_nosq(x1, y1, x2, y2):
    """ユークリッド距離sqなし"""
    return (x1-x2)**2 + (y1-y2)**2


def manhattan(x1, y1, x2, y2):
    """マンハッタン距離"""
    return abs(x1-x2) + abs(y1-y2)


def chebyshev(x1, y1, x2, y2):
    """チェビシェフ距離"""
    return max(abs(x1-x2), abs(y1-y2))



# ==========================
# grid
# ==========================

MOVE4 = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1)
]

MOVE8 = [
    (1, 0), (-1, 0),
    (0, 1), (0, -1),
    (1, 1), (1, -1),
    (-1, 1), (-1, -1)
]





# ==========================
# sort
# ==========================

def quick_sort(A):
    if len(A) <= 1:
        return A

    pivot = A[len(A)//2]

    left = [x for x in A if x < pivot]
    mid = [x for x in A if x == pivot]
    right = [x for x in A if x > pivot]

    return quick_sort(left) + mid + quick_sort(right)


def merge_sort(A):
    if len(A) <= 1:
        return A

    mid = len(A)//2

    L = merge_sort(A[:mid])
    R = merge_sort(A[mid:])

    res = []

    i = j = 0

    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            res.append(L[i])
            i += 1
        else:
            res.append(R[j])
            j += 1

    res.extend(L[i:])
    res.extend(R[j:])

    return res

"""
昇順ソート
A = [5, 2, 8, 1, 9]

B = quick_sort(A)

print(B) 

降順ソート
A = [5,2,8,1,9]

B = quick_sort(A)

print(B[::-1])
"""

# ==========================
# bfs
# ==========================



def bfs(G, s):
    dist = [-1] * len(G)

    dist[s] = 0

    q = deque([s])

    while q:
        v = q.popleft()

        for nv in G[v]:
            if dist[nv] != -1:
                continue

            dist[nv] = dist[v] + 1
            q.append(nv)

    return dist

# ==========================
# dfs
# ==========================

def dfs(G, s):
    seen = [False] * len(G)

    def rec(v):
        seen[v] = True

        for nv in G[v]:
            if not seen[nv]:
                rec(nv)

    rec(s)

    return seen

"""
G=[
[1,2],   0に関してつながってるやつ
[0,3],
[0],
[1]
]


print(bfs(G,0))-> [0,1,1,2] 距離0karano
"""
def dfs_stack(G, s):
    seen = [False] * len(G)

    st = [s]

    while st:
        v = st.pop()

        if seen[v]:
            continue

        seen[v] = True

        for nv in G[v]:
            st.append(nv)

    return seen
"""
G=[
[1,2],   0に関してつながってるやつ
[0,3],
[0],
[1]
]


print(dfs(G,0))-> [True,True,True,True]
"""



"""
all([])を使うと、全部がTrueの時だけTrueを返すようになる
"""
# ==========================
# output
# ==========================

def YES():
    print("Yes")


def NO():
    print("No")





"""
PL = lambda a: print(*a) ##a = [1, 2, 3, 4, 5]
                         ##PL(a)                 --> 1 2 3 4 5

dame = lambda: print("-1")
YN = lambda x: print(("No", "Yes")[x])  ### YN(a == b)

"""


#################################################################
"""

#====必要な分だけの二次元配列====
n = int(input())
a = []
for _ in range(n):
    row = list(map(int, input().split()))
    a.append(row[1:]) # 必要な長さ分だけ追加すればよい


#(,)とやったら空白になって出るから平気
#タプルにするときは　append((1,2))のようににじゅうかっこ

#extend バラバラに投入
#append 1 2 3 4みたいなのを　[1 2 3 4]として入れられる

##sorted( ,reverse=True)  で降順に。　　a.sort()か　b = sorted(a) で昇順ソート
#(*b)で中身全部を出す

#整数の出力ほしいなら//で基本的に（/だと2.0とかに

文字数カウントはs.count('abc')




for c, cnt in rle(s):
    print(c, cnt)で[(,),(,)]みたいなやつで、タプルの中身とそれぞれ対応させられる
mx[c] = max(mx.get(c, 0), cnt)文字 c の連続長の最大値を更新
    """

"""
def add(a: int, b: int) -> int:
    return a + b codon



    
"""


"""
| 言語            | popの動作     |
| ------------- | ---------- |
| C++           | 消すだけ（返さない） |
| Python(heapq) | 消して値を返す    |
"""

"""
それぞれの初期化
二次元配列lst2d = [[0] * 3 for i in range(3)]　or list2di
class PQ:#最小値
    def __init__(self):
        self.data = []

class Queue:
    def __init__(self):
        self.data = deque()
class Stack:
    def __init__(self):
        self.data = []


    def push_back(self, x):
        末尾に追加
        self.data.append(x)

    def append(self, x):
        末尾に追加
        self.data.append(x)

    def push_front(self, x):
        先頭に追加
        self.data.appendleft(x)

    def pop_back(self):
        末尾を取り出して削
        return self.data.pop()

    def pop_front(self):
        先頭を取り出して削除
return self.data.popleft()
"""
##II() にする必要あり!!!!!!!!!!!!!!
##II() にする必要あり!!!!!!!!!!!!!! 
##list =,int= とかは使えないので気を付けて
##for でスライス使うとき、ｊがｉよりでかくならないためにrange(i,j)とかにする！
#dict.fromkeys,setで重複けせる(list(dict.fromkeys(l))) list(set(my_list)) setは順番変わる可能性ある
#find は文字列、indexはlistだがこれはある前提なので　in をつかって、Trueかどうかはんだん
# set は{}　append　ー>>>add
#max(data, key=lambda x: x[0]) でたプルの一番眼だけ
# komozi islower()
#oomozi isupper()        ()を忘れるなあああああああああああああああ
#基本的に、PQなどはすでに関数があるので、selfPQ や　PQ1
#XOR の計算には ^ の演算子が割り当てられている
# list は　append!!!!!!!!!!!!!!!!!!!＋＝だめ!!!!!!!!!!!!!!!!!!! * で要素だよ！！“
#改行させない場合は  print("Hello, ", end="") 空白開けてのときは" "にする \n 忘れないこと
#pop()　listの場合最後尾が消える。pop(0)にしてせんとう 
###A,Bこれはcpython,pypyになってますか？
#####################################
#####################################
##############code code##############

N = II()
t = []
for i in range(N):
    k,j = IMI()
    t.append((k+j,i))
get = max(t,key=lambda x: x[0])
print(get[1]+1) 

提出情報

ジャッジ結果