import itertools
import math
import string
import sys
from bisect import bisect_left as bi_l
from bisect import bisect_right as bi_r
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from operator import or_, xor

sys.setrecursionlimit(10**7)
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353


using_numpy = 1
import networkx as nx
import numpy as np
from numba import i8, njit
from scipy import optimize
from scipy.ndimage import distance_transform_cdt
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import (
    connected_components,
    csgraph_to_dense,
    maximum_flow,
    minimum_spanning_tree,
    shortest_path,
)
from scipy.spatial import ConvexHull
from scipy.special import comb


class Algebra:
  class Modular(int):
    def __init__(self, n, mod=MOD):
      self.value = n
      self.mod = mod

    def __str__(self): return f'{self.value}'

    def __add__(self, other):
      return self.__class__((self.value + other.value) % self.mod)
    def __sub__(self, x): return self.__class__((self.value - x.value) % self.mod)
    def __mul__(self, x): return self.__class__((self.value * x.value) % self.mod)
    def __pow__(self, x): return self.__class__(pow(self.value, x.value, self.mod))

    def __lt__(self, x): return self.value < x.value
    def __le__(self, x): return self.value <= x.value
    def __eq__(self, x): return self.value == x.value
    def __ne__(self, x): return self.value != x.value
    def __gt__(self, x): return self.value > x.value
    def __ge__(self, x): return self.value >= x.value



  class SemiGroup:
    pass
  class Monoid:
    pass
  class Group:
    pass
  class SemiRing:
    pass
  class Ring:
    pass


  @staticmethod
  def identity(n):
    if using_numpy:
      return np.identity(n, dtype=np.int64)
    else:
      a = [[0]*n for _ in range(n)]
      for i in range(n): a[i][i] = 1
      return a

  @staticmethod
  def dot(a, b):
    if using_numpy:
      return np.dot(a, b)
    else:
      h, w, l = len(a), len(b[0]), len(b)
      assert len(a[0]) == l
      c = [[0]*w for _ in range(h)]
      for i in range(h):
        for j in range(w):
          for k in range(l):
            c[i][j] += a[i][k]*b[k][j]
      return c

  @classmethod
  def matrix_pow(cls, a, n, mod=10**9+7):
    m = len(a)
    b = cls.identity(m)
    while n:
      if n&1: b = cls.dot(b, a)
      n >>= 1; a = cls.dot(a, a)
      if using_numpy:
        a %= mod; b %= mod
      else:
        for i in range(m):
          for j in range(m):
            a[i][j] %= mod
            b[i][j] %= mod
    return b

  @staticmethod
  def bitwise_dot(a, b):
    if using_numpy:
      return np.bitwise_xor.reduce(a[:,None,:] & b.T[None,:,:], axis=-1)
    else:
      h, w, l = len(a), len(b[0]), len(b)
      assert len(a[0]) == l
      c = [[0]*w for _ in range(h)]
      for i in range(h):
        for j in range(w):
          for k in range(l):
            c[i][j] ^= a[i][k]&b[k][j]
      return c

  @classmethod
  def bitwise_mat_pow(cls, a, n):
    if n==0: return np.eye(len(a), dtype=np.uint32)*((1<<32)-1)
    res = cls.bitwise_mat_pow(a, n//2)
    res = cls.bitwise_dot(res, res)
    return cls.bitwise_dot(res, a) if n&1 else res


  @staticmethod
  def cumprod(a, mod):
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= mod
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= mod
    return np.ravel(a)[:l]

  @classmethod
  def generate_fac_ifac(cls, n, p=MOD):
    if using_numpy:
      fac = np.arange(n+1); fac[0] = 1; fac = cls.cumprod(fac, p)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = cls.cumprod(ifac, p)[n::-1]
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
    return fac, ifac

  class Kitamasa:
    pass


mint = Algebra.Modular


class NumberTheory:
  class PrimeNumbers: # pn
    def __init__(self, n=2*10**6):
      self.is_prime, self.prime_nums = self.find(n)

    def __call__(self, n): return self.is_prime[n]
    def __iter__(self): return iter(self.prime_nums)
    def __getitem__(self, key): return self.prime_nums[key]

    @staticmethod
    def find(n): # Sieve of eratosthenes
      if using_numpy:
        is_prime = np.ones(n+1, dtype=np.bool); is_prime[:2] = 0
        for i in range(2, int(n**.5)+1):
          if is_prime[i]: is_prime[i*2::i] = 0
        prime_nums = np.flatnonzero(is_prime)
      else:
        is_prime = [True]*(n+1); is_prime[0] = is_prime[1] = 0
        for i in range(2, int(n**.5)+1):
          if not is_prime[i]: continue
          for j in range(i*2, n+1, i): is_prime[j] = 0
        prime_nums = [i for i in range(2, n+1) if is_prime[i]]
      return is_prime, prime_nums

    @lru_cache(maxsize=None)
    def factorize(self, n):
      res = defaultdict(int)
      if n < 2: return res
      for p in self:
        if p*p > n: break
        while n%p == 0: res[p] += 1; n //= p
        if n == 1: return res
      res[n] = 1; return res

    def factorize_factorial(self, n):
      res = defaultdict(int)
      for i in range(2, n+1):
        for p, c in self.factorize(i).items(): res[p] += c
      return res

  @classmethod
  @lru_cache(maxsize=None)
  def gcd(cls, a, b): return cls.gcd(b, a%b) if b else abs(a)
  @classmethod
  def lcm(cls, a, b): return abs(a // cls.gcd(a, b) * b)

  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return sorted(divisors)

  @staticmethod
  def base_convert(n, b):
    if not n: return [0]
    res = []
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res.append(r)
    return res



class Combinatorics:
  @classmethod
  @lru_cache(maxsize=None)
  def choose(cls, n, r, mod=None):
    if r > n or r < 0: return 0
    if r == 0: return 1
    res = cls.choose(n-1,r,mod) + cls.choose(n-1,r-1,mod)
    if mod: res %= mod
    return res

  class CombinationsMod:
    def __init__(self, n=2*10**6, mod=MOD):
      self.__mod = mod
      self.fac, self.ifac = Algebra.generate_fac_ifac(n, mod)

    def __call__(self, n, r): return self.__choose(n, r)

    def __choose(self, n, r):
      bl = (0<=r) & (r<=n)
      p = self.__mod
      return bl * self.fac[n] * self.ifac[r] % p * self.ifac[n-r] % p

    def make_nchoose_table(self, n):
      p = self.__mod
      r = len(self.__fac)-1
      if using_numpy:
        n_choose = np.arange(n+1, n-r, -1); n_choose[0] = 1
        n_choose = Algebra.cumprod(n_choose, p)*self.ifac%p
      else:
        n_choose = [None]*(r+1); n_choose[0] = 1
        for i in range(r): n_choose[i+1] = n_choose[i]*(n-i)%p
        for i in range(1,r+1): n_choose[i] = n_choose[i]*self.ifac[i]%p
      return n_choose

  @classmethod
  def permutations(cls, a, r=None, i=0):
    a = list(a); n = len(a)
    if r is None: r = n
    res = []
    if r > n or i > r: return res
    if i == r: return [tuple(a[:r])]
    for j in range(i, n): a[i],a[j] = a[j],a[i]; res += cls.permutations(a, r, i+1)
    return res

  @staticmethod
  def combinations(a, r):
    a = tuple(a)
    n = len(a)
    if r > n: return
    indices = list(range(r))
    yield a[:r]
    while True:
      for i in range(r-1, -1, -1):
        if indices[i] != i+n-r: break
      else: return
      indices[i] += 1
      for j in range(i+1, r): indices[j] = indices[j-1]+1
      yield tuple(a[i] for i in indices)



class DP:
  @staticmethod
  def LIS(a):
    res = [inf] * len(a)
    for x in a: res[bi_l(res, x)] = x
    return res


class String:
  @staticmethod
  def z_algorithm(s):
    n = len(s)
    a = [0] * n; a[0] = n
    l = r = -1
    for i in range(1, n):
      if r >= i: a[i] = min(a[i-l], r-i)
      while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
      if i+a[i] >= r: l, r = i, i+a[i]
    return a


class GeometryTopology:
  class Graph:
    class __Edge:
      def __init__(self, weight=1, capacity=1, **args):
        self.weight = weight
        self.capacity = capacity

      def __str__(self):
        return f'weight: {self.weight}, cap: {self.capacity}'

    class __Node:
      def __init__(self, **args):
        pass

    def __init__(self, n=0):
      self.__N = n
      self.nodes = [None] * n
      self.edges = [{} for _ in range(n)]

    def add_node_info(self, v, **args): self.nodes[v] = self.__Node(**args)

    def add_edge(self, u, v, update=False, **args):
      if not update and v in self.edges[u]: return
      self.edges[u][v] = self.__Edge(**args)

    def get_size(self): return self.__N

    def bfs(self, src=0):
      n = self.__N
      self.depth = self.lv = lv = [None]*n; lv[src] = 0 # depth in tree, or level in general graph.
      self.dist = dist = [inf]*n; dist[src] = 0 # dist for only tree.
      self.parent = par = [None]*n; par[src] = src
      q = deque([src])
      while q:
        u = q.popleft()
        for v, e in self.edges[u].items():
          if e.capacity == 0 or lv[v] is not None: continue
          lv[v], dist[v], par[v] = lv[u]+1, dist[u]+e.weight, u
          q.append(v)
      return dist

    def dinic(self, src, sink):
      def flow_to_sink(u, flow_in):
        if u == sink: return flow_in
        flow = 0
        for v, e in self.edges[u].items():
          if e.capacity == 0 or self.lv[v] <= self.lv[u]: continue
          f = flow_to_sink(v, min(flow_in, e.capacity))
          if not f: continue
          self.edges[u][v].capacity -= f
          if u in self.edges[v]: self.edges[v][u].capacity += f
          else: self.add_edge(v, u, capacity=f)
          flow_in -= f
          flow += f
        return flow

      flow = 0
      while True:
        self.bfs(src)
        if self.lv[sink] is None: return flow
        flow += flow_to_sink(src, inf)

    def ford_fulkerson(self):
      pass

    def push_relabel(self):
      pass

    def floyd_warshall(self):
      n = self.__N
      d = [[inf]*n for _ in range(n)]
      for u in range(n):
        d[u][u] = 0
        for v, e in self.edges[u].items(): d[u][v] = e.weight
      for w in range(n):
        for u in range(n):
          for v in range(n):
            d[u][v] = min(d[u][v], d[u][w]+d[w][v])
      return d

    def dijkstra(self, src, paths_cnt=False, mod=None):
      dist = [inf] * self.__N; dist[src] = 0
      visited = [False] * self.__N
      paths = [0] * self.__N; paths[src] = 1
      q = [(0, src)]
      while q:
        d, u = heappop(q)
        if visited[u]: continue
        visited[u] = True
        for v, e in self.edges[u].items():
          dv = d + e.weight
          if dv > dist[v]: continue
          elif dv == dist[v]:
            paths[v] += paths[u]
            if mod: paths[v] %= mod
            continue
          paths[v], dist[v] = paths[u], dv
          heappush(q, (dv, v))
      if paths_cnt: return dist, paths
      else: return dist

    def astar(self, src, tgt, heuristic_func):
      cost = [inf] * self.__N
      q = [(heuristic_func(src, tgt), 0, src)]
      while q:
        _, c, u = heappop(q)
        if u == tgt: return c
        if cost[u] != inf: continue
        cost[u] = c
        for v, e in self.edges[u].items():
          if cost[v] != inf: continue
          h = heuristic_func(v, tgt)
          nc = c + e.weight
          heappush(q, (h+nc, nc, v))
      return inf

    def bellman_ford(self, src):
      n = self.__N
      d = [inf] * n; d[src] = 0
      for _ in range(n-1):
        for u in range(n):
          for v, e in self.edges[u].items(): d[v] = min(d[v], d[u]+e.weight)
      for u in range(n):
        for v, e in self.edges[u].items():
          if d[u]+e.weight < d[v]: raise Exception('found negative cycle.')
      return d

    def bfs01(self, src=0):
      d = [inf]*self.__N; d[src] = 0
      q = deque([src])
      while q:
        u = q.popleft()
        for v, e in self.edges[u].items():
          dv = d[u] + e.weight
          if d[v] <= dv: continue
          d[v] = dv
          if e.weight: q.append(v)
          else: q.appendleft(v)
      return d


    def find_ancestors(self): # tree doubling.
      self.__ancestors = ancestors = [self.parent]
      for _ in range(max(self.depth).bit_length()):
        ancestors.append([ancestors[-1][u] for u in ancestors[-1]])


    def find_dist(self, u, v):
      return self.dist[u]+self.dist[v]-2*self.dist[self.__find_lca(u, v)]


    def __find_lca(self, u, v):
      du, dv = self.depth[u], self.depth[v]
      if du > dv:
        u, v = v, u
        du, dv = dv, du

      d = dv - du
      for i in range(d.bit_length()): # up-stream
        if d>>i&1: v = self.__ancestors[i][v]
      if v == u: return v

      for i in range(du.bit_length()-1, -1, -1): # find direct child of LCA.
        nu, nv = self.__ancestors[i][u], self.__ancestors[i][v]
        if nu == nv: continue
        u, v = nu, nv

      return self.__ancestors[0][u]

    def init_dsu(self): # disjoint set union (union-find)
      n = self.__N
      self.parent = list(range(n))
      self.rank = [0] * n
      self.size = [1] * n

    def find(self, u):
      if self.parent[u] == u: return u
      self.parent[u] = self.find(self.parent[u])
      return self.parent[u]

    def unite(self, u, v):
      u, v = self.find(u), self.find(v)
      if u == v: return
      if self.rank[u] < self.rank[v]: u,v = v,u
      self.parent[v] = u
      self.size[u] += self.size[v]
      self.rank[u] = max(self.rank[u], self.rank[v]+1)

    def same(self, u, v): return self.find(u)==self.find(v)

    def groups(self):
      n = self.__N
      groups = [[] for _ in range(n)]
      for u in range(n): groups[self.find(u)].append(u)
      return groups
      # return [g for g in groups if g]




    def scc(self): # strongly connected components
      n = self.__N
      visited, q, root, r = [False]*n, [], [None]*n, 0
      gg = self.__class__(n)
      for u in range(n):
        for v in self.edges[u]: gg.add_edge(v, u)

      def dfs(u):
        if visited[u]: return
        visited[u] = True
        for v in self.edges[u]: dfs(v)
        q.append(u)

      def rev_dfs(u, r):
        if root[u] is not None: return
        root[u] = r
        for v in gg.edges[u]: rev_dfs(v, r)

      for u in range(n): dfs(u)
      for u in q[::-1]: rev_dfs(u, r); r += 1
      return root


    def kruskal(self): # minimum spanning tree
      n = self.__N
      uf = self.__class__(n); uf.init_dsu()
      edges = sorted([(u,v,e.weight) for u in range(n) for v,e in self.edges[u].items()], key=lambda x: x[2])
      g = self.__class__(n)
      d = 0
      for u, v, w in edges:
        if uf.same(u,v): continue
        uf.unite(u, v); g.add_edge(u, v, weight=w); d += w
      return g, d

    def prim(self, src=0, return_parent=False): # minimum spanning tree
      n = self.__N
      g = self.__class__(n)
      parent, visited, dist = [None]*n, [False]*n, 0
      q = [(0, (src, src))]
      while q:
        d, (w, u) = heappop(q)
        if visited[u]: continue
        visited[u], parent[u] = True, w; dist += d; g.add_edge(w,u, weight=d)
        for v, e in self.edges[u].items():
          if not visited[v]: heappush(q, (e.weight, (u,v)))
      if return_parent: return g, dist, parent
      return g, dist

    def boruvka(self): # minimum spanning tree
      n = self.__N
      uf = self.__class__(n); uf.init_dsu()
      g = self.__class__(n)
      d = 0

      def dfs(u):
        if visited[u]: return (inf, (None, None))
        visited[u] = True
        cand = []
        for v, e in self.edges[u].items():
          if uf.same(u,v): cand.append(dfs(v)); continue
          cand.append((e.weight, (u,v)))
        return sorted(cand)[0]

      while len(set(uf.parent))!=1:
        edges, visited = [], [False]*n
        for u in range(n):
          if visited[u]: continue
          edges.append(dfs(u))
        for w, (u, v) in edges:
          if uf.same(u,v): continue
          g.add_edge(u,v, weight=w); uf.unite(u,v); d += w
        for u in range(n): uf.find(u)

      return g, d

    def tsp(self): # traveling salesperson problem
      pass



  @staticmethod
  def triangle_area(p0, p1, p2, signed=False):
    x1, y1, x2, y2 = p1[0]-p0[0], p1[1]-p0[1], p2[0]-p0[0], p2[1]-p0[1]
    return (x1*y2 - x2*y1)/2 if signed else abs(x1*y2 - x2*y1)/2

  @classmethod
  def intersect(cls, seg1, seg2):
    (p1, p2), (p3, p4) = seg1, seg2
    t1 = cls.triangle_area(p1, p2, p3, signed=True)
    t2 = cls.triangle_area(p1, p2, p4, signed=True)
    t3 = cls.triangle_area(p3, p4, p1, signed=True)
    t4 = cls.triangle_area(p3, p4, p2, signed=True)
    return (t1*t2<0) & (t3*t4<0)


def cumxor(a): return reduce(xor, a, 0)
def cumor(a): return reduce(or_, a, 0)

def bit_count(n):
  cnt = 0
  while n: cnt += n&1; n >>= 1
  return cnt


class AtCoder:
  class ABC001:
    @staticmethod
    def a():
      h1, h2 = map(int, sys.stdin.read().split()); print(h1-h2)

    @staticmethod
    def d():
      def to_minuites(x):
        q, r = divmod(x, 100)
        return 60*q + r

      def to_hmform(x):
        q, r = divmod(x, 60)
        return 100*q + r

      n = int(sys.stdin.readline().rstrip())
      term = [0] * 2001
      for _ in range(n):
        s, e = map(to_minuites, map(int, sys.stdin.readline().rstrip().split('-')))
        s = s//5 * 5
        e = (e+4)//5 * 5
        term[s] += 1
        term[e+1] -= 1
      for i in range(2000):
        term[i+1] += term[i]

      res = []
      raining = False
      for i in range(2001):
        if term[i]:
          if not raining:
            s = i
            raining = True
        elif raining:
          res.append((s, i-1))
          raining = False
      for s, e in res:
        print(f'{to_hmform(s):04}-{to_hmform(e):04}')




  class ABC002:
    @staticmethod
    def a():
      print(max(map(int, sys.stdin.readline().split())))

    @staticmethod
    def b():
      vowels = set('aeiou')
      print(''.join([c for c in sys.stdin.readline().rstrip() if c not in vowels]))

    @staticmethod
    def c():
      print(GeometryTopology.triangle_area(*map(int, sys.stdin.readline().split())))

    @staticmethod
    def d():
      n, m = map(int, sys.stdin.readline().split())
      edges = set((x-1, y-1) for x, y in zip(*[map(int, sys.stdin.read().split())]*2))
      print(max(len(s) for i in range(1, 1<<n) for s in [[j for j in range(n) if i>>j&1]] if all((x, y) in edges for x, y in itertools.combinations(s, 2))))

    @staticmethod
    def d_2():
      n, m = map(int, sys.stdin.readline().split())
      relations = [1<<i for i in range(n)]
      for x, y in zip(*[map(int, sys.stdin.read().split())]*2):
        relations[x] |= 1<<(y-1); relations[y] |= 1<<(x-1)
      res = 0
      for i in range(1<<n):
        s, cnt = (1<<n)-1, 0
        for j in range(n):
          if i>>j & 1: t &= relations[j] | 1<<j; cnt += 1
        if s&i == i: res = max(res, cnt)
      print(res)

  class ABC003:
    @staticmethod
    def a():
      print((int(sys.stdin.readline().rstrip())+1)*5000)
    @staticmethod
    def b():
      atcoder = set('atcoder')
      s, t = sys.stdin.read().split()
      print(all(s[i]==t[i] or s[i]=='@' and t[i] in atcoder or t[i]=='@' and s[i] in atcoder for i in range(len(s))) and 'You can win' or 'You will lose')

    @staticmethod
    def c():
      n, k, *r = map(int, sys.stdin.read().split()); print(reduce(lambda x, y: (x+y)/2, sorted(r)[-k:], 0))

  class ABC004:
    @staticmethod
    def a():
      print(int(sys.stdin.readline().rstrip())*2)
    @staticmethod
    def b():
      for l in [sys.stdin.readline().rstrip() for _ in range(4)][::-1]: print(l[::-1])
    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())%30
      res = list(range(1, 7))
      for i in range(n): i %= 5; res[i], res[i+1] = res[i+1], res[i]
      print(*res, sep='')



  class ABC005:
    @staticmethod
    def a():
      x, y = map(int, sys.stdin.readline().split())
      print(y//x)
    @staticmethod
    def b():
      n, *t = map(int, sys.stdin.read().split())
      print(min(t))
    @staticmethod
    def c():
      t = int(sys.stdin.readline().rstrip())
      n = int(sys.stdin.readline().rstrip())
      a = [int(x) for x in sys.stdin.readline().split()]
      m = int(sys.stdin.readline().rstrip())
      b = [int(x) for x in sys.stdin.readline().split()]
      i = 0
      for p in b:
        if i == n: print('no'); return
        while p-a[i] > t:
          i += 1
          if i == n: print('no'); return
        if a[i] > p: print('no'); return
        i += 1
      print('yes')
    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
      s = d.cumsum(axis=0).cumsum(axis=1)
      s = np.pad(s, 1)
      max_del = np.zeros((n+1, n+1), dtype=np.int64)
      for y in range(1, n+1):
        for x in range(1, n+1):
          max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
      res = np.arange(n**2+1)[:, None]
      i = np.arange(1, n+1)
      res = max_del[i, np.minimum(res//i, n)].max(axis=1)
      q = int(sys.stdin.readline().rstrip())
      p = np.array(sys.stdin.read().split(), dtype=np.int64)
      print(*res[p], sep='\n')


  class ABC006:
    @staticmethod
    def a():
      n = sys.stdin.readline().rstrip()
      if '3' in n: print('YES')
      elif int(n)%3 == 0: print('YES')
      else: print('NO')

    @staticmethod
    def b():
      mod = 10007
      a = np.eye(N=3, k=-1, dtype=np.int64); a[0] = 1
      n = int(sys.stdin.readline().rstrip())
      a = Algebra.matrix_pow(a, n-1, mod)
      print(a[2][0])


    @staticmethod
    def c():
      n, m = map(int, sys.stdin.readline().split())
      cnt = [0, 0, 0]
      if m == 1: cnt = [-1, -1, -1]
      else:
        if m & 1: m -= 3; cnt[1] += 1; n -= 1
        cnt[2] = m//2 - n
        cnt[0] = n - cnt[2]
      if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
      else: print(*cnt, sep=' ')

    @staticmethod
    def d():
      n, *c = map(int, sys.stdin.read().split())
      lis = [inf]*n
      for x in c: lis[bi_l(lis, x)] = x
      print(n - bi_l(lis, inf))

  class ABC007:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      print(n-1)
    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      if s == 'a': print(-1)
      else: print('a')
    @staticmethod
    def c():
      r, c = map(int, sys.stdin.readline().split())
      sy, sx = map(int, sys.stdin.readline().split())
      gy, gx = map(int, sys.stdin.readline().split())
      sy -= 1; sx -=1; gy -= 1; gx -= 1
      maze = [sys.stdin.readline().rstrip() for _ in range(r)]
      queue = deque([(sy, sx)])
      dist = np.full((r, c), np.inf); dist[sy, sx] = 0
      while queue:
        y, x = queue.popleft()
        for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
          i += y; j += x
          if maze[i][j] == '#' or dist[i, j] != np.inf: continue
          dist[i, j] = dist[y, x] + 1
          queue.append((i, j))
      print(int(dist[gy, gx]))
    @staticmethod
    def d():
      ng = set([4, 9])
      def count(d):
        return d if d<=4 else d-1
      def f(n):
        x = [int(d) for d in str(n)]
        flg = True
        dp = 0
        for d in x:
          dp = dp*8 + flg*count(d)
          if d in ng: flg = False
        return n-(dp+flg)
      a, b = map(int, sys.stdin.readline().split())
      print(f(b) - f(a-1))

  class ABC008:
    @staticmethod
    def a():
      s, t = map(int, sys.stdin.readline().split())
      print(t-s+1)
    @staticmethod
    def b():
      n, *s = sys.stdin.read().split()
      res = defaultdict(int)
      for name in s: res[name] += 1
      print(sorted(res.items(), key=lambda x: x[1])[-1][0])
    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      c = n - np.count_nonzero(a[:, None]%a, axis=1)
      print(np.sum((c+1)//2/c))

    @staticmethod
    def d():
      w, h, n, *xy = map(int, sys.stdin.read().split())
      *xy, = zip(*([iter(xy)]*2))

      @lru_cache(maxsize=None)
      def count(x1, y1, x2, y2):
        res = 0
        for x, y in xy:
          if not (x1 <= x <= x2 and y1 <= y <= y2): continue
          cnt = (x2-x1) + (y2-y1) + 1
          cnt += count(x1, y1, x-1, y-1)
          cnt += count(x1, y+1, x-1, y2)
          cnt += count(x+1, y1, x2, y-1)
          cnt += count(x+1, y+1, x2, y2)
          res = max(res, cnt)
        return res
      print(count(1, 1, w, h))


  class ABC009:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      print((n+1)//2)
    @staticmethod
    def b():
      n, *a = map(int, sys.stdin.read().split())
      print(sorted(set(a))[-2])
    @staticmethod
    def c():
      n, k = map(int, sys.stdin.readline().split())
      s = list(sys.stdin.readline().rstrip())
      cost = [1]*n
      r = k
      for i in range(n-1):
        q = []
        for j in range(i+1, n):
          if s[j] < s[i] and cost[i]+cost[j] <= r:
            heappush(q, (s[j], cost[i]+cost[j], -j))
        if not q: continue
        _, c, j = heappop(q); j = -j
        s[i], s[j] = s[j], s[i]
        r -= c
        cost[i] = cost[j] = 0
      print(''.join(s))

    @staticmethod
    def d():
      k, m = map(int, sys.stdin.readline().split())
      a = np.array([int(x) for x in sys.stdin.readline().split()])
      c = np.array([int(x) for x in sys.stdin.readline().split()])
      mask = (1<<32) - 1
      d = np.eye(k, k, -1, dtype=np.uint32) * mask; d[0] = c
      if m <= k: print(a[m-1]); return
      # print(Algebra.bitwise_mat_pow(d, m-k))
      # print(Algebra.bitwise_dot(Algebra.bitwise_mat_pow(d, m-k), a[::-1].reshape(-1, 1))[0].item())
      print(Algebra.bitwise_dot(Algebra.bitwise_mat_pow(d, m-k), a[::-1].reshape(-1, 1))[0][0])



  class ABC010:
    @staticmethod
    def a():
      print(sys.stdin.readline().rstrip()+'pp')
    @staticmethod
    def b():
      n, *a = map(int, sys.stdin.read().split())
      tot = 0
      for x in a:
        c = 0
        while x%2==0 or x%3==2:
          x -= 1
          c += 1
        tot += c
      print(tot)
    @staticmethod
    def c():
      sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
      x, y = np.array(xy).reshape(-1, 2).T
      def dist(x1, y1, x2, y2):
        return np.sqrt((x2-x1)**2 + (y2-y1)**2)
      ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
      print(ans)

    @staticmethod
    def d():
      n, g, e = map(int, sys.stdin.readline().split())
      p = [int(x) for x in sys.stdin.readline().split()]
      x, y = [], []
      for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        x.append(a); y.append(b)
        x.append(b); y.append(a)
      for a in p:
        x.append(a)
        y.append(n)
      if not x:
        print(0)
        return
      c = [1] * len(x)
      min_cut = maximum_flow(csr_matrix((c, (x, y)), (n+1, n+1)), source=0, sink=n).flow_value
      print(min_cut)

    @staticmethod
    def d_2():
      n, g, e = map(int, sys.stdin.readline().split())
      graph = nx.DiGraph()
      graph.add_nodes_from(range(n+1))
      for p in [int(x) for x in sys.stdin.readline().split()]:
        graph.add_edge(p, n, capacity=1)
      for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph.add_edge(a, b, capacity=1)
        graph.add_edge(b, a, capacity=1)
      print(nx.minimum_cut_value(graph, 0, n))

    @staticmethod
    def d_3():
      n, q, m = map(int, sys.stdin.readline().split())
      g = GeometryTopology.Graph(n+1)
      # for i in range(n+1): g.add_node(i)
      for p in [int(x) for x in sys.stdin.readline().split()]:
        g.add_edge(p, n, capacity=1)
      for a, b in zip(*[map(int, sys.stdin.read().split())]*2):
        g.add_edge(a, b, capacity=1)
        g.add_edge(b, a, capacity=1)
      print(g.dinic(0, n))



  class ABC011:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      print(n%12+1)
    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      print(s[0].upper()+s[1:].lower())
    @staticmethod
    def c():
      n, *ng = map(int, sys.stdin.read().split())
      ng = set(ng)
      if n in ng: print('NO')
      else:
        r = 100
        while n > 0:
          if r == 0: print('NO'); return
          for i in range(3, 0, -1):
            if (n-i) in ng: continue
            n -= i
            r -= 1
            break
          else: print('NO'); return
        print('YES')

    @staticmethod
    def d():
      n, d, x, y = map(int, sys.stdin.read().split())
      x, y = abs(x), abs(y)
      if x%d or y%d: print(0); return
      x, y = x//d, y//d
      r = n - (x+y)
      if r < 0 or r&1: print(0); return

      res = 0
      half_p = pow(1/2, n)
      for d in range(r//2 + 1): # 0 <= d <= r//2, south
        south, north = d, y+d
        west = (r - 2*d)//2
        res += half_p * comb(n, south, exact=True) * comb(n-south, north, exact=True)\
                      * comb(n-south-north, west, exact=True) * half_p
      print(res)


  class ABC012:
    @staticmethod
    def a():
      a, b = map(int, sys.stdin.readline().split())
      print(b, a)

    @staticmethod
    def b():
      n = int(sys.stdin.readline().rstrip())
      h, n = divmod(n, 3600)
      m, s = divmod(n, 60)
      print(f'{h:02}:{m:02}:{s:02}')

    @staticmethod
    def c():
      n = 2025 - int(sys.stdin.readline().rstrip())
      res = []
      for i in range(1, 10):
        if n%i != 0 or n//i > 9: continue
        res.append(f'{i} x {n//i}')
      print(*sorted(res), sep='\n')

    @staticmethod
    def d():
      n, m, *abt = map(int, sys.stdin.read().split())
      a, b, t = np.array(abt).reshape(m, 3).T
      res = shortest_path(csr_matrix((t, (a-1, b-1)), (n, n)), method='FW', directed=False)
      print(res.max(axis=-1).min().astype(np.int64))

    @staticmethod
    def d_2():
      n, m, *abt = map(int, sys.stdin.read().split())
      g = GeometryTopology.Graph(n)
      for a, b, t in zip(*[iter(abt)]*3):
        a -= 1; b -= 1
        g.add_edge(a, b, weight=t)
        g.add_edge(b, a, weight=t)

      print(min(max(d) for d in g.floyd_warshall()))



  class ABC013:
    @staticmethod
    def a():
      print(ord(sys.stdin.readline().rstrip()) - ord('A') + 1)

    @staticmethod
    def b():
      a, b = map(int, sys.stdin.read().split())
      d = abs(a - b)
      print(min(d, 10-d))

    @staticmethod
    def c():
      n, h, a, b, c, d, e = map(int, sys.stdin.read().split())
      y = np.arange(n+1)
      x = (n*e-h-(d+e)*y)//(b+e) + 1
      np.maximum(x, 0, out=x)
      np.minimum(x, n-y, out=x)
      print(np.amin(a*x + c*y))

    @staticmethod
    def d():
      n, m, d, *a = map(int, sys.stdin.read().split())
      res = list(range(n))
      def swap(i, j): res[i], res[j] = res[j], res[i]
      for i in a[::-1]: swap(i-1, i)
      res = np.array(res)
      def binary_method(a, p):
        b = np.arange(n)
        while p:
          if p&1: b = a[b]
          p >>= 1
          a = a[a]
        return b
      print(*(binary_method(res, d)+1), sep='\n')

  class ABC014:
    @staticmethod
    def a():
      a, b = map(int, sys.stdin.read().split())
      print((a+b-1)//b * b - a)

    @staticmethod
    def b():
      n, x, *a = map(int, sys.stdin.read().split())
      print(sum(a[i] for i in range(n) if x>>i&1))

    @staticmethod
    def c():
      n, *ab = map(int, sys.stdin.read().split())
      a, b = np.array(ab).reshape(n, 2).T
      res = np.zeros(10**6+2, dtype=np.int64)
      np.add.at(res, a, 1)
      np.subtract.at(res, b+1, 1)
      np.cumsum(res, out=res)
      print(res.max())

    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      g = GeometryTopology.Graph(n)
      for _ in range(n-1):
        x, y = map(int, sys.stdin.readline().split())
        x -= 1; y -= 1
        g.add_edge(x, y, weight=1)
        g.add_edge(y, x, weight=1)

      g.bfs(0)
      g.find_ancestors()

      q, *ab = map(int, sys.stdin.read().split())
      for a, b in zip(*[iter(ab)]*2):
        a -= 1; b -= 1
        print(g.find_dist(a, b) + 1)

  class ABC015:
    @staticmethod
    def a():
      a, b = sys.stdin.read().split()
      print(a if len(a) > len(b) else b)

    @staticmethod
    def b():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      print(np.ceil(a[np.nonzero(a)[0]].sum() / np.count_nonzero(a)).astype(np.int8))

    @staticmethod
    def c():
      n, k, *t = map(int, sys.stdin.read().split())
      t = np.array(t).reshape(n, k)
      x = np.zeros((1, 1), dtype=np.int8)
      for i in range(n):
        x = x.reshape(-1, 1) ^ t[i]
      print('Found' if np.count_nonzero(x==0) > 0 else 'Nothing')

    @staticmethod
    def d():
      w, n, k, *ab = map(int, sys.stdin.read().split())
      dp = np.zeros((k+1, w+1), dtype=np.int32)
      for a, b in zip(*[iter(ab)]*2): np.maximum(dp[1:,a:], dp[:-1,:-a]+b, out=dp[1:,a:])
      print(dp[k][w])


  class ABC016:
    @staticmethod
    def a():
      m, d = map(int, sys.stdin.readline().split())
      print('YES' if m%d == 0 else 'NO')

    @staticmethod
    def b():
      a, b, c = map(int, sys.stdin.readline().split())
      f1, f2 = a+b==c, a-b==c
      if f1 & f2: print('?')
      elif f1 & (~f2): print('+')
      elif (~f1) & f2: print('-')
      else: print('!')

    @staticmethod
    def c():
      n, _, *ab = map(int, sys.stdin.read().split())
      f = [0] * n
      for a, b in zip(*[iter(ab)]*2):
        a -= 1; b -= 1
        f[a] |= 1<<b
        f[b] |= 1<<a
      res = [bit_count(cumor(f[j] for j in range(n) if f[i]>>j&1) & ~(f[i] | 1<<i)) for i in range(n)]
      print(*res, sep='\n')

    @staticmethod
    def d():
      sx, sy, gx, gy = map(int, sys.stdin.readline().split())
      seg1 = ((sx, sy), (gx, gy))
      n = int(sys.stdin.readline().rstrip())
      p1 = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, 2).T
      p2 = np.hstack((p1[:, 1:], p1[:, :1]))
      seg2 = (p1, p2)
      print(np.count_nonzero(GeometryTopology.intersect(seg1, seg2))//2 + 1)

  class ABC017:
    @staticmethod
    def a():
      s, e = np.array(sys.stdin.read().split(), dtype=np.int16).reshape(3, 2).T
      print((s // 10 * e).sum())

    @staticmethod
    def b():
      choku_tail = set('ch, o, k, u'.split(', '))
      def is_choku(s):
        if s == '': return True
        if len(s)>=1 and (s[-1] in choku_tail) and is_choku(s[:-1]): return True
        if len(s)>=2 and (s[-2:] in choku_tail) and is_choku(s[:-2]): return True
        return False
      print('YES' if is_choku(sys.stdin.readline().rstrip()) else 'NO')

    @staticmethod
    def c():
      n, m, *lrs = map(int, sys.stdin.read().split())
      l, r, s = np.array(lrs).reshape(n, 3).T
      score = np.zeros((m+1, ), dtype=np.int32)
      np.add.at(score, l-1, s)
      np.subtract.at(score, r, s)
      np.cumsum(score, out=score)
      print(s.sum() - score[:m].min())

    @staticmethod
    def d():
      n, m, *f = map(int, sys.stdin.read().split())
      prev = [0] * (n+1)
      tmp = defaultdict(int)
      for i in range(n):
        prev[i+1] = tmp[f[i]]
        tmp[f[i]] = i+1

      dp = [0] * (n+1); dp[0] = 1
      l, s = 0, dp[0]
      for i in range(1, n+1):
        while l < prev[i]:
          s = (s - dp[l]) % MOD
          l += 1
        dp[i] = s
        s = (s + dp[i]) % MOD
      print(dp[n])

  class ABC018:
    @staticmethod
    def a():
      *a, = map(int, sys.stdin.read().split())
      a = sorted(enumerate(a), key=lambda x: -x[1])
      res = [None] * 3
      for i in range(3):
        res[a[i][0]] = i+1
      print(*res, sep='\n')

    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      n, *lr = map(int, sys.stdin.read().split())
      for l, r in zip(*[iter(lr)]*2):
        l -= 1; r -= 1
        s = s[:l] + s[l:r+1][::-1] + s[r+1:]
      print(s)

    @staticmethod
    def c():
      r, c, k = map(int, sys.stdin.readline().split())
      s = np.array([list(s) for s in sys.stdin.read().split()])
      s = np.pad(s, 1, constant_values='x')

      a = np.zeros_like(s, dtype=np.float64)
      a[s=='o'] = np.inf
      for i in range(1, r+1): np.minimum(a[i-1,:]+1, a[i,:], out=a[i,:])
      for i in range(r, 0, -1): np.minimum(a[i+1,:]+1, a[i,:], out=a[i,:])
      for j in range(1, c+1): np.minimum(a[:,j-1]+1, a[:,j], out=a[:,j])
      for j in range(c, 0, -1): np.minimum(a[:,j+1]+1, a[:,j], out=a[:,j])
      print(np.count_nonzero(a>=k))

    @staticmethod
    def c_2():
      r, c, k = map(int, sys.stdin.readline().split())
      s = np.array([list(s) for s in sys.stdin.read().split()])
      s = np.pad(s, 1, constant_values='x')
      a = (s=='o').astype(np.int16)
      a = distance_transform_cdt(a, metric='taxicab')
      print(np.count_nonzero(a>=k))

    @staticmethod
    def d():
      n, m, p, q, r, *xyz = map(int, sys.stdin.read().split())
      x, y, z = np.array(xyz).reshape(r, 3).T
      h = np.zeros((n, m), dtype=np.int32); h[x-1, y-1] = z
      g = np.array([*itertools.combinations(range(n), p)])
      print(np.sort(h[g].sum(axis=1), axis=1)[:,-q:].sum(axis=1).max())


  class ABC019:
    @staticmethod
    def a():
      *a, = map(int, sys.stdin.readline().split())
      print(sorted(a)[1])

    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip() + '$'
      cnt = 0
      prev = '$'
      t = ''
      for c in s:
        if c == prev: cnt += 1; continue
        t += prev+str(cnt)
        prev = c; cnt = 1
      print(t[2:])

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      res = set()
      for x in a:
        while not x&1:
          x >>= 1
        res.add(x)
      print(len(res))

    @staticmethod
    def d():
      def inquire(u, v):
        print(f'? {u} {v}'.format(u, v), flush=True)
        return int(sys.stdin.readline().rstrip())

      n = int(sys.stdin.readline().rstrip())
      u = sorted([(inquire(1, v), v) for v in range(2, n+1)])[-1][1]
      d = max((inquire(u, v)) for v in range(1, n+1) if u!=v)
      print(f'! {d}')

  class ABC020:
    @staticmethod
    def a():
      print('ABC' if int(sys.stdin.readline().rstrip())==1 else 'chokudai')

    @staticmethod
    def b():
      a, b = sys.stdin.readline().split()
      print(int(a+b) * 2)

    @staticmethod
    def c():
      h, w, t = map(int, sys.stdin.readline().split())
      s = [list(s) for s in sys.stdin.read().split()]
      for i in range(h):
        for j in range(w):
          if s[i][j] == 'S': sy, sx = i, j
          if s[i][j] == 'G': gy, gx = i, j
      s[sy][sx] = s[gy][gx] = '.'
      source, target = sy*w+sx, gy*w+gx

      def heuristic_function(u, v=target):
        uy, ux = divmod(u, w)
        vy, vx = divmod(v, w)
        return abs(vy-uy) + abs(ux-vx)

      def min_time(x):
        g = GeometryTopology.Graph(h*w)
        # g = nx.DiGraph()

        for i in range(h):
          for j in range(w):
            u = i*w + j
            if i > 0: g.add_edge(u, (i-1)*w+j, weight=(1 if s[i-1][j]=='.' else x))
            if i < h-1: g.add_edge(u, (i+1)*w+j, weight=(1 if s[i+1][j]=='.' else x))
            if j > 0: g.add_edge(u, i*w+j-1, weight=(1 if s[i][j-1]=='.' else x))
            if j < w-1: g.add_edge(u, i*w+j+1, weight=(1 if s[i][j+1]=='.' else x))

        return g.dijkstra(source)[target]
        return g.astar(source, target, heuristic_function)
        # return nx.dijkstra_path_length(g, source, target)
        # return nx.astar_path_length(g, source, target, heuristic_function)

      def binary_search():
        lo, hi = 1, t+1
        while lo+1 < hi:
          x = (lo+hi)//2
          if min_time(x) > t:
            hi = x
          else:
            lo = x
        return lo

      print(binary_search())

    @staticmethod
    def d():
      n, k = map(int, sys.stdin.readline().split())
      div = sorted(NumberTheory.find_divisors(k))
      l = len(div)
      s = [0] * l
      for i, d in enumerate(div): s[i] = (1+n//d)*(n//d)//2 * d % MOD
      for i in range(l-1, -1, -1):
        for j in range(i+1, l):
          if div[j]%div[i]: continue
          s[i] = (s[i]-s[j])%MOD

      print(sum(s[i]*k//div[i]%MOD for i in range(l))%MOD) # ans is LCM.

  class ABC021:
    @staticmethod
    def a():
      n  = int(sys.stdin.readline().rstrip())
      s = [1<<i for i in range(5) if n>>i&1]
      print(len(s), *s, sep='\n')

    @staticmethod
    def b():
      n, a, b, k, *p = map(int, sys.stdin.read().split())
      print('YES' if len(set(p)|set([a, b])) == k+2 else 'NO')

    @staticmethod
    def c():
      n, a, b, m, *xy = map(int, sys.stdin.read().split())
      x, y = np.array(xy).reshape(m, 2).T - 1
      a -= 1; b -= 1
      g = csgraph_to_dense(csr_matrix((np.ones(m), (x, y)), (n, n), dtype=np.int8))
      g = np.logical_or(g, g.T)
      paths = np.zeros(n, dtype=np.int64).reshape(-1, 1)
      paths[a, 0] = 1
      while not paths[b, 0]:
        paths = np.dot(g, paths) % MOD
      print(paths[b, 0])

    @staticmethod
    def c_2():
      n, a, b, m, *xy = map(int, sys.stdin.read().split())
      a -= 1; b -= 1
      g = GeometryTopology.Graph()

      for x, y in zip(*[iter(xy)]*2):
        x -= 1; y -= 1
        g.add_edge(x, y, weight=1)
        g.add_edge(y, x, weight=1)

      dist, paths = g.dijkstra(a, paths_cnt=True, mod=MOD)
      print(paths[b])

    @staticmethod
    def d():
      n, k = map(int, sys.stdin.read().split())
      cn = Combinatorics.CombinationsMod()
      print(cn(n+k-1, k))


  class ABC022:
    @staticmethod
    def a():
      n, s, t, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      np.cumsum(a, out=a)
      print(((s<=a) & (a<=t)).sum())

    @staticmethod
    def b():
      n, *a = map(int, sys.stdin.read().split())
      c = Counter(a)
      print(sum(c.values())-len(c))

    @staticmethod
    def c():
      n, m, *uvl = map(int, sys.stdin.read().split())
      u, v, l = np.array(uvl).reshape(m, 3).T
      u -= 1; v -= 1
      g = csgraph_to_dense(csr_matrix((l, (u,v)), (n,n)))
      g += g.T
      g[g==0] = np.inf
      dist0 = g[0].copy()
      g[0] = 0; g[:, 0] = 0
      dist = shortest_path(g, method='FW', directed=False)
      u, v = np.array([*itertools.combinations(range(1,n), 2)]).T
      res = (dist0[u]+dist[u,v]+dist0[v]).min()
      print(-1 if res==np.inf else int(res))

    @staticmethod
    def d():
      n, *ab = map(int, sys.stdin.read().split())
      c = np.array(ab).reshape(2,n,2)
      g = c.mean(axis=1)
      d = np.sqrt(((c-g[:,None,:])**2).sum(axis=-1)).sum(axis=1)
      print(d[1]/d[0])


  class ABC023:
    @staticmethod
    def a():
      print(sum(divmod(int(sys.stdin.readline().rstrip()), 10)))

    @staticmethod
    def b():
      n, s = sys.stdin.read().split()
      n = int(n)
      t = 'b'
      for i in range(n//2):
        if i%3==0: t = 'a'+t+'c'
        elif i%3==1: t = 'c'+t+'a'
        else: t = 'b'+t+'b'
      print(n//2 if t==s else -1)

    @staticmethod
    def b_2():
      n, s = sys.stdin.read().split()
      n = int(n)
      if n&1^1: print(-1); return
      a = list('abc')
      i = (1-n//2)%3
      for c in s:
        if c != a[i]:
          print(-1); return
        i = (i+1) % 3
      print(n//2)

    @staticmethod
    def c():
      h, w, k, n, *rc = map(int, sys.stdin.read().split())
      r, c = np.array(rc).reshape(n,2).T - 1
      rb = np.bincount(r, minlength=h)
      cb = np.bincount(c, minlength=w)
      rbb = np.bincount(rb, minlength=k+1)
      cbb = np.bincount(cb, minlength=k+1)
      tot = (rbb[:k+1]*cbb[k::-1]).sum()
      real = np.bincount(rb[r]+cb[c]-1, minlength=k+1)
      print(tot-real[k-1]+real[k])

    @staticmethod
    def d():
      n, *hs = map(int, sys.stdin.read().split())
      h, s = np.array(hs).reshape(n,2).T

      t = np.arange(n)
      def is_ok(x): return np.all(np.sort((x-h)//s) >= t)
      def binary_search():
        lo, hi = 0, 10**14
        while lo+1 < hi:
          x = (lo+hi)//2
          if is_ok(x): hi = x
          else: lo = x
        return hi

      print(binary_search())

  class ABC024:
    @staticmethod
    def a():
      a, b, c, k, s, t = map(int, sys.stdin.read().split())
      print(a*s + b*t - c*(s+t)*(s+t>=k))

    @staticmethod
    def b():
      n, t, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      print(np.minimum(a[1:]-a[:-1], t).sum() + t)

    @staticmethod
    def c():
      n, d, k, *lrst = map(int, sys.stdin.read().split())
      lrst = np.array(lrst)
      lr = lrst[:2*d].reshape(d,2)
      s, t = lrst[2*d:].reshape(k,2).T
      day = np.zeros((k,),dtype=np.int32)
      for i in range(d):
        l, r = lr[i]
        move = (l<=s)&(s<=r)&(s!=t)
        reach = move&(l<=t)&(t<=r)
        s[move&(s<t)] = r
        s[move&(s>t)] = l
        s[reach] = t[reach]; day[reach] = i+1
      print(*day, sep='\n')

    @staticmethod
    def d():
      a, b, c = map(int, sys.stdin.read().split())
      p = MOD
      denom = pow(a*b%p - b*c%p + c*a%p, p-2, p)
      w = (b*c-a*b)%p*denom%p
      h = (b*c-a*c)%p*denom%p
      print(h,w)

  class ABC025:
    @staticmethod
    def a():
      s, n = sys.stdin.read().split()
      n = int(n)
      i, j = divmod(n-1, 5)
      print(s[i]+s[j])

    @staticmethod
    def b():
      n, a, b = map(int, sys.stdin.readline().split())
      res = defaultdict(int)
      for _ in range(n):
        s, d = sys.stdin.readline().split()
        d = int(d)
        res[s] += min(max(d,a),b)
      res = res['East'] - res['West']
      if res == 0: ans = 0
      elif res > 0: ans = f'East {res}'
      else: ans = f'West {-res}'
      print(ans)

    @staticmethod
    def c():
      b = [0] * 6
      for i in range(2):
        *row, = map(int, sys.stdin.readline().split())
        for j in range(3):
          b[i*3+j] = row[j]
      c = [0] * 8
      for i in range(3):
        *row, = map(int, sys.stdin.readline().split())
        for j in range(2):
          c[i*3+j] = row[j]
      tot = sum(b) + sum(c)

      @lru_cache(maxsize=None)
      def f(s=tuple(0 for _ in range(9))):
        if all(s):
          res = 0
          for i in range(6): res += (s[i]==s[i+3])*b[i]
          for i in range(8): res += (s[i]==s[i+1])*c[i]
          return res
        cand = [i for i in range(9) if not s[i]]
        flg = len(cand)&1
        s = list(s)
        res = []
        for i in cand:
          s[i] = (flg^1)+1
          res.append(f(tuple(s)))
          s[i] = 0
        return sorted(res, reverse=flg)[0]

      a = f(); b = tot-a
      print(a)
      print(b)



  class ABC026:
    @staticmethod
    def a():
      a = int(sys.stdin.readline().rstrip())
      print(a//2 * (a-a//2))

    @staticmethod
    def b():
      n, *r = map(int, sys.stdin.read().split())
      s = np.pi * np.array([0]+r)**2; s.sort()
      res = s[n::-2].sum() - s[n-1::-2].sum()
      print(res)

    @staticmethod
    def c():
      n, *b = map(int, sys.stdin.read().split())
      g = GeometryTopology.Graph()
      for i in range(1, n): g.add_edge(b[i-1]-1, i, weight=1)

      def f(u=0):
        if not g.edges[u]: return 1
        s = [f(v) for v in g.edges[u]]
        return max(s) + min(s) + 1

      print(f())

    @staticmethod
    def d():
      a, b, c = map(int, sys.stdin.readline().split())
      def f(t): return a*t + b*np.sin(c*t*np.pi) - 100
      print(optimize.brenth(f, 0, 200))


  class ABC027:
    @staticmethod
    def a():
      l = [int(l) for l in sys.stdin.readline().split()]
      l.sort()
      print(l[2] if l[0]==l[1] else l[0])

    @staticmethod
    def b():
      n, *a = map(int, sys.stdin.read().split())
      m, r = divmod(sum(a), n)
      if r: print(-1); return
      population = 0
      towns = 0
      cnt = 0
      for x in a:
        population += x
        towns += 1
        if population/towns != m: cnt+=1; continue
        population, towns = 0, 0
      print(cnt)

    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())
      flg = n.bit_length()&1^1
      t = 0
      x = 1
      while x <= n:
        t += 1
        x = 2*x+1 if t&1^flg else 2*x
      print('Aoki' if t&1 else 'Takahashi')


  class ABC028:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      print('Bad' if n<60 else 'Good' if n<90 else 'Great' if n<100 else 'Perfect')

    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      cnt = Counter(s)
      print(*[cnt.get(c, 0) for c in 'ABCDEF'])

    @staticmethod
    def c():
      a, b, c, d, e = map(int, sys.stdin.readline().split())
      print(max(b+c+e, a+d+e))

    @staticmethod
    def d():
      n, k = map(int, sys.stdin.readline().split())
      c = 3*2*(n-k)*(k-1) + 3*(n-1) + 1
      print(c/n**3)


  class ABC029:
    @staticmethod
    def a():
      print(sys.stdin.readline().rstrip()+'s')

    @staticmethod
    def b():
      print(sum('r' in s for s in sys.stdin.read().split()))

    @staticmethod
    def c():
      print(*[''.join(s) for s in itertools.product('abc', repeat=int(sys.stdin.readline().rstrip()))], sep='\n')

    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      print(sum(n//10**(i+1)*10**i + min(max((n%10**(i+1)-10**i+1), 0), 10**i) for i in range(9)))

  class ABC030:
    @staticmethod
    def a():
      a, b, c, d = map(int, sys.stdin.readline().split())
      e, f = b*c, d*a
      print('TAKAHASHI' if e>f else 'AOKI' if f>e else 'DRAW')

    @staticmethod
    def b():
      n, m = map(int, sys.stdin.readline().split())
      n = (n%12 + m/60)*30; m *= 6
      d = abs(n-m)
      print(min(d, 360-d))

    @staticmethod
    def c():
      n, m = map(int, sys.stdin.readline().split())
      x, y = map(int, sys.stdin.readline().split())
      a = [int(x) for x in sys.stdin.readline().split()]
      b = [int(x) for x in sys.stdin.readline().split()]

      t = 0
      p = 1
      cnt = 0
      while True:
        if p:
          i = bi_l(a, t)
          if i == n: break
          t = a[i] + x
        else:
          i = bi_l(b, t)
          if i == m: break
          t = b[i] + y
          cnt += 1
        p ^= 1
      print(cnt)

    @staticmethod
    def d():
      n, a = map(int , sys.stdin.readline().split()); a -= 1
      k = sys.stdin.readline().rstrip()
      b = [int(x)-1 for x in sys.stdin.readline().split()]

      c = [None] * n
      for i in range(n+1):
        if str(i)==k: print(a+1);return
        if c[a] is not None: l, d = i-c[a], c[a];break
        c[a] = i; a = b[a]

      r = [None] * len(k); r[0] = 1
      for i in range(len(k)-1): r[i+1] = r[i]*10%l
      k = [int(c) for c in k][::-1]
      d = (sum(r[i]*k[i] for i in range(len(k)))-d) % l
      for _ in range(d): a = b[a]
      print(a+1)

    @staticmethod
    def d_2():
      n, a, k, *b = map(int, sys.stdin.read().split())
      a -= 1; b = [x-1 for x in b]
      c = [None]*n
      for i in range(n+1):
        if i==k: print(a+1); return
        if c[a] is not None:
          for _ in range((k-c[a])%(i-c[a])): a = b[a]
          print(a+1); return
        c[a] = i; a = b[a]


  class ABC031:
    @staticmethod
    def a():
      a, d = map(int, sys.stdin.readline().split())
      if a > d: a,d = d,a
      print((a+1)*d)

    @staticmethod
    def b():
      l, h, n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      res = np.maximum(l-a, 0)
      res[a>h] = -1
      print(*res, sep='\n')

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      np.cumsum(a[::2], out=a[::2])
      np.cumsum(a[1::2], out=a[1::2])
      a = list(a) + [0]*2

      def score(i, j):
        if i > j: i, j = j, i
        if (j-i)&1: x, y = a[j-1]-a[i-2], a[j]-a[i-1]
        else: x, y = a[j]-a[i-2], a[j-1]-a[i-1]
        return x, y

      res = -inf
      for i in range(n):
        s = -inf
        for j in range(n):
          if i==j: continue
          x, y = score(i, j)
          if y>s: s,t = y,x
        res = max(res, t)
      print(res)

    @staticmethod
    def d():
      k, m = map(int, sys.stdin.readline().split())
      *vw, = zip(*[iter(sys.stdin.read().split())]*2)
      for l in itertools.product((1,2,3), repeat=k):
        s = dict()
        for v, w in vw:
          i = 0
          for d in v:
            d = int(d)-1
            j = i+l[d]
            if j > len(w): break
            t = w[i:j]
            if d in s and s[d] != t: break
            s[d] = t
            i = j
          else:
            if i == len(w): continue
          break
        else:
          for i in range(k): print(s[i])
          return


  class ABC032:
    @staticmethod
    def a():
      a, b, n = map(int, sys.stdin.read().split())
      l = NumberTheory.lcm(a, b)
      print((n+l-1)//l*l)

    @staticmethod
    def b():
      s, k = sys.stdin.read().split()
      k = int(k)
      res = set()
      for i in range(len(s)-k+1):
        res.add(s[i:i+k])
      print(len(res))

    @staticmethod
    def c():
      n, k, *s = map(int, sys.stdin.read().split())
      if 0 in s: print(n); return
      if k == 0: print(0); return
      res, tmp, l = 0, 1, 0
      for r in range(n):
        tmp *= s[r]
        while tmp > k: tmp //= s[l]; l+=1
        res = max(res, r-l+1)

      print(res)

  class ABC033:
    @staticmethod
    def a():
      print('SAME' if len(set(sys.stdin.readline().rstrip()))==1 else 'DIFFERENT')

    @staticmethod
    def b():
      n = int(sys.stdin.readline().rstrip())
      res = dict()
      for _ in range(n):
        s, p = sys.stdin.readline().split()
        res[s] = int(p)
      tot = sum(res.values())
      for s, p in res.items():
        if p > tot/2: print(s); return
      print('atcoder')

    @staticmethod
    def c():
      s = sys.stdin.readline().rstrip()
      print(sum(not '0' in f for f in s.split('+')))


  class ABC034:
    @staticmethod
    def a():
      x, y = map(int, sys.stdin.readline().split())
      print('Better' if y>x else 'Worse')

    @staticmethod
    def b():
      n = int(sys.stdin.readline().rstrip())
      print(n+1 if n&1 else n-1)

    @staticmethod
    def c():
      h, w = map(int, sys.stdin.read().split())
      choose = Combinatorics.CombinationsMod()
      print(choose(h+w-2, h-1))

    @staticmethod
    def d():
      n, k, *wp = map(int, sys.stdin.read().split())
      w, p = np.array(wp).reshape(-1, 2).T
      def f(x):
        return np.sort(w*(p-x))[-k:].sum()
      print(optimize.bisect(f, 0, 100))

  class ABC035:
    @staticmethod
    def a():
      w, h = map(int, sys.stdin.readline().split())
      print('4:3' if 4*h==3*w else '16:9')

    @staticmethod
    def b():
      s, t = sys.stdin.read().split()
      y = x = z = 0
      for c in s:
        if c == '?': z += 1
        elif c == 'L': x -= 1
        elif c == 'R': x += 1
        elif c == 'D': y -= 1
        elif c == 'U': y += 1
      d = abs(y)+abs(x)
      print(d+z if t=='1' else max(d-z, (d-z)&1))

    @staticmethod
    def c():
      n, q, *lr = map(int, sys.stdin.read().split())
      l, r = np.array(lr).reshape(q, 2).T
      res = np.zeros(n+1, dtype=int)
      np.add.at(res, l-1, 1)
      np.subtract.at(res, r, 1)
      np.cumsum(res, out=res)
      res = res&1
      print(''.join(map(str, res[:-1])))

    @staticmethod
    def d():
      n, m, t = map(int, sys.stdin.readline().split())
      point = np.array(sys.stdin.readline().split(), dtype=int)
      a, b, c = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(m, 3).T
      a -= 1; b -= 1
      d_1 = shortest_path(csr_matrix((c, (a, b)), (n, n)), method='D', directed=True, indices=0)
      d_2 = shortest_path(csr_matrix((c, (b, a)), (n, n)), method='D', directed=True, indices=0)
      print(int(np.amax((t-(d_1+d_2))*point)))

  class ABC036:
    @staticmethod
    def a():
      a, b = map(int, sys.stdin.readline().split())
      print((b+a-1)//a)

    @staticmethod
    def b():
      n, *s = sys.stdin.read().split()
      n = int(n)
      for j in range(n):
        row = ''
        for i in range(n-1, -1, -1):
          row += s[i][j]
        print(row)

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      b = [None]*n
      prev = None
      j = -1
      for i, x in sorted(enumerate(a), key=lambda x: x[1]):
        if x != prev: j += 1
        b[i] = j
        prev = x
      print(*b, sep='\n')

    @staticmethod
    def d():
      n, *ab = map(int, sys.stdin.read().split())
      edges = [[] for _ in range(n)]
      for a, b in zip(*[iter(ab)]*2):
        a -= 1; b -= 1
        edges[a].append(b)
        edges[b].append(a)
      parent = [None]*n
      def count(u):
        black, white = 1, 1
        for v in edges[u]:
          if v == parent[u]: continue
          parent[v] = u
          b, w = count(v)
          black *= w; black %= MOD
          white *= (b+w)%MOD; white %= MOD
        return black, white
      print(sum(count(0))%MOD)

  class ABC037:
    @staticmethod
    def a():
      a, b, c = map(int, sys.stdin.readline().split())
      print(c//min(a, b))

    @staticmethod
    def b():
      n, q, *lrt = map(int, sys.stdin.read().split())
      a = np.zeros(n, dtype=int)
      for l, r, t in zip(*[iter(lrt)]*3):
        a[l-1:r] = t
      print(*a, sep='\n')

    @staticmethod
    def c():
      n, k, *a = map(int, sys.stdin.read().split())
      a = np.array([0]+a)
      np.cumsum(a, out=a)
      s = (a[k:] - a[:-k]).sum()
      print(s)

    @staticmethod
    def d():
      h, w, *a = map(int, sys.stdin.read().split())
      p = [None]*(h*w)
      def paths(k):
        if p[k]: return p[k]
        p[k] = 1
        i, j = divmod(k,w)
        if j>0 and a[k]>a[k-1]: p[k] += paths(k-1)
        if j<w-1 and a[k]>a[k+1]: p[k] += paths(k+1)
        if i>0 and a[k]>a[k-w]: p[k] += paths(k-w)
        if i<h-1 and a[k]>a[k+w]: p[k] += paths(k+w)
        p[k] %= MOD; return p[k]
      print(sum(paths(i) for i in range(h*w))%MOD)


  class ABC038:
    @staticmethod
    def a():
      s = sys.stdin.readline().rstrip()
      print('YES' if s[-1]=='T' else 'NO')

    @staticmethod
    def b():
      a, b, c, d = map(int, sys.stdin.read().split())
      print('YES' if a==c or b==c or a==d or b==d else 'NO')

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a += [-1]
      cnt = n
      tmp = 1
      for i in range(n):
        if a[i+1] > a[i]:
          tmp += 1
        else:
          cnt += tmp*(tmp-1)//2
          tmp = 1
      print(cnt)

    @staticmethod
    def d():
      n, *wh = map(int, sys.stdin.read().split())
      a = [x[1] for x in sorted(zip(*[iter(wh)]*2), key=lambda x: (x[0], -x[1]))]
      print(bi_l(DP.LIS(a), inf))

  class ABC039:
    @staticmethod
    def a():
      a, b, c = map(int, sys.stdin.readline().split())
      print((a*b+b*c+c*a)*2)

    @staticmethod
    def b():
      x = int(sys.stdin.readline().rstrip())
      for n in range(1, int(x**0.5)+1):
        if pow(n, 4)==x:
          print(n); return


    @staticmethod
    def c():
      board = 'WBWBWWBWBWBW' * 3
      convert = 'Do, *, Re, *, Mi, Fa, *, So, *, La, *, Si'.split(', ')
      s = sys.stdin.readline().rstrip()
      print(convert[board.index(s)])


    @staticmethod
    def d():
      h, w = map(int, sys.stdin.readline().split())
      s = ''.join(sys.stdin.read().split())
      white = set()
      for i in range(h*w):
        if s[i]=='#': continue
        l = 0 if i%w==0 else -1
        r = 0 if (i+1)%w==0 else 1
        white |= {i+dy+dx for dy in range(-w, w+1, w) for dx in range(l,r+1)}
      black_before = set(range(h*w)) - white
      black_after = set()
      for i in black_before:
        l = 0 if i%w==0 else -1
        r = 0 if (i+1)%w==0 else 1
        black_after |= {i+dy+dx for dy in range(-w, w+1, w) for dx in range(l,r+1)}
      black_after &= set(range(h*w))
      for i in range(h*w):
        if s[i]=='#' and not i in black_after: print('impossible'); return
      print('possible')
      for i in range(h):
        print(''.join(['#' if i*w+j in black_before else '.' for j in range(w)]))




  class ABC040:
    @staticmethod
    def a():
      n, x = map(int, sys.stdin.readline().split())
      print(min(x-1, n-x))

    @staticmethod
    def b():
      n = int(sys.stdin.readline().rstrip())
      res = inf
      for i in range(1, int(n**.5)+1):
        res = min(res, n//i-i+n%i)
      print(res)

    @staticmethod
    def c():
      n, *h = map(int, sys.stdin.read().split())
      h = [h[0]]+h
      cost = [None] * (n+1); cost[0] = cost[1] = 0
      for i in range(2, n+1):
        cost[i] = min(
          cost[i-2] + abs(h[i]-h[i-2]),
          cost[i-1] + abs(h[i]-h[i-1])
        )
      print(cost[n])

    @staticmethod
    def d():
      n, m = map(int, sys.stdin.readline().split())
      uf = GeometryTopology.Graph(n); uf.init_dsu()
      queue = []
      for _ in range(m):
        a, b, y = map(int, sys.stdin.readline().split())
        heappush(queue, (-(2*y), a-1, b-1))
      q = int(sys.stdin.readline().rstrip())
      for i in range(q):
        v, y = map(int, sys.stdin.readline().split())
        heappush(queue, (-(2*y+1), v-1, i))
      res = [None] * q
      while queue:
        y, i, j = heappop(queue)
        if y&1:
          res[j] = uf.size[uf.find(i)]
        else:
          uf.unite(i, j)
      print(*res, sep='\n')

  class ABC041:
    @staticmethod
    def a():
      s, i = sys.stdin.read().split()
      i = int(i)
      print(s[i-1])

    @staticmethod
    def b():
      a, b, c = map(int, sys.stdin.readline().split())
      ans = a * b % MOD * c % MOD
      print(ans)

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      for i, h in sorted(enumerate(a), key=lambda x: -x[1]):
        print(i+1)

    @staticmethod
    def d():
      n, _, *xy = map(int, sys.stdin.read().split())
      g = [0]*n
      for x, y in zip(*[iter(xy)]*2): g[x-1] |= 1<<(y-1)
      res = [0]*(1<<n); res[0] = 1
      for i in range(1<<n):
        for j in range(n):
          if i>>j&1^1: continue
          if not(g[j]&i): res[i] += res[i&~(1<<j)]
      print(res[-1])



  class ABC042:
    @staticmethod
    def a():
      a = [int(x) for x in sys.stdin.readline().split()]
      c = Counter(a)
      print('YES' if c[5]==2 and c[7]==1 else 'NO')

    @staticmethod
    def b():
      n, l, *s = sys.stdin.read().split()
      print(''.join(sorted(s)))

    @staticmethod
    def c():
      n, k, *d = sys.stdin.read().split()
      l = len(n)
      ok = sorted(set(string.digits)-set(d))
      cand = [int(''.join(p)) for p in itertools.product(ok, repeat=l)] + [int(min(x for x in ok if x > '0')+min(ok)*l)]
      print(cand[bi_l(cand, int(n))])

    @staticmethod
    def d():
      h, w, a, b = map(int, sys.stdin.read().split())
      combinations = Combinatorics.CombinationsMod(n=2*10**5, mod=MOD)
      i = np.arange(h-a, h)
      ng = np.sum(combinations(i+b-1, i) * combinations(h-i+w-b-2, h-1-i) % MOD)
      print((combinations(h+w-2, h-1)-ng)%MOD)


  class ABC043:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      print((1+n)*n//2)

    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      t = ''
      for c in s:
        if c == 'B': t = t[:-1]
        else: t += c
      print(t)

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      x = np.around(a.sum()/n).astype(int)
      print(np.sum((a-x)**2))

    @staticmethod
    def d():
      s = sys.stdin.readline().rstrip()
      n = len(s)
      for i in range(n-1):
        if s[i] == s[i+1]: print(i+1, i+2); return
      for i in range(n-2):
        if s[i] == s[i+2]: print(i+1, i+3); return
      print(-1, -1)

  class ABC044:
    @staticmethod
    def a():
      n, k, x, y = map(int, sys.stdin.read().split())
      print(min(n,k)*x + max(0,n-k)*y)

    @staticmethod
    def b():
      res = set(c&1 for c in Counter(sys.stdin.readline().rstrip()).values())
      print('Yes' if len(res)==1 and res.pop()==0 else 'No')

    @staticmethod
    def c():
      n, a, *x = map(int, sys.stdin.read().split())
      dp = np.zeros((n+1, 2501), dtype=np.int64); dp[0,0] = 1
      for v in x: dp[1:,v:] += dp[:-1,:-v]
      i = np.arange(1, n+1)
      print(dp[i, i*a].sum())

    @staticmethod
    def c_2():
      n, a, *x = map(int, sys.stdin.read().split())
      for i in range(n): x[i] -= a

      s = defaultdict(int); s[0] = 1
      for i in range(n):
        ns = s.copy()
        for k, v in s.items(): ns[k+x[i]] += v
        s = ns
      print(s[0]-1)



    @staticmethod
    def d():
      pass

  class ABC045:
    @staticmethod
    def a():
      a, b, h = map(int, sys.stdin.read().split())
      print((a+b)*h//2)

    @staticmethod
    def b():
      a, b, c = sys.stdin.read().split()
      d = {'a': a[::-1], 'b': b[::-1], 'c': c[::-1]}
      nx = 'a'
      while 1:
        if not d[nx]: print(nx.upper()); return
        d[nx], nx = d[nx][:-1], d[nx][-1]

    @staticmethod
    def c():
      def c(l): return pow(2, max(0,l-1))
      s = sys.stdin.readline().rstrip()
      n = len(s)
      print(sum(int(s[i:j+1])*c(i)*c(n-1-j) for i in range(n) for j in range(i, n)))

    @staticmethod
    def d():
      h, w, n, *ab = map(int, sys.stdin.read().split())
      c = defaultdict(int)
      for y, x in zip(*[iter(ab)] * 2):
        y -= 1; x -= 1
        for dy, dx in itertools.product(range(-1, 2), repeat=2):
          i, j = y+dy, x+dx
          if not(0<i<h-1 and 0<j<w-1): continue
          c[(i,j)] += 1
      c = Counter(c.values())
      c[0] = (h-2)*(w-2)-sum(c.values())
      for i in range(10): print(c[i])


  class ABC046:
    @staticmethod
    def a():
      print(len(set(sys.stdin.readline().split())))

    @staticmethod
    def b():
      n, k = map(int, sys.stdin.readline().split())
      print(k*pow(k-1, n-1))

    @staticmethod
    def c():
      n, *xy = map(int, sys.stdin.read().split())
      a, b = 1, 1
      for x, y in zip(*[iter(xy)]*2):
        n = max((a+x-1)//x, (b+y-1)//y)
        a, b = n*x, n*y
      print(a+b)

    @staticmethod
    def d():
      c = Counter(sys.stdin.readline().rstrip())
      print((c['g']-c['p'])//2)



  class ABC047:
    @staticmethod
    def a():
      c = sorted(map(int, sys.stdin.readline().split()))
      print('Yes' if c[0]+c[1]==c[2] else 'No')

    @staticmethod
    def b():
      w, h, n, *xyf = map(int, sys.stdin.read().split())
      l, r, d, u = 0, w, 0, h
      for x, y, f in zip(*[iter(xyf)]*3):
        if f == 1: l = max(l, x)
        if f == 2: r = min(r, x)
        if f == 3: d = max(d, y)
        if f == 4: u = min(u, y)
      print(max(0, r-l)*max(0, u-d))

    @staticmethod
    def c():
      s = sys.stdin.readline().rstrip()
      print(sum(s[i]!=s[i+1] for i in range(len(s)-1)))

    @staticmethod
    def d():
      mn, mx, c = inf, -1, 0
      n, t, *a = map(int, sys.stdin.read().split())
      for p in a:
        if p-mn == mx: c += 1
        elif p-mn>mx: mx, c = p-mn, 1
        mn = min(mn, p)
      print(c)

  class ABC048:
    @staticmethod
    def a():
      def initial(s): return s[0].upper()
      print(''.join(map(initial, sys.stdin.readline().split())))

    @staticmethod
    def b():
      a, b, x = map(int, sys.stdin.readline().split())
      print(b//x - (a-1)//x) # if a=0, (a-1)/x is rounded down to -1.

    @staticmethod
    def c():
      n, x, *a = map(int, sys.stdin.read().split())
      cnt = prev = 0
      for i in range(n):
        d = prev+a[i] - x
        prev = a[i]
        if d <= 0: continue
        cnt += d; prev -= d
      print(cnt)

    @staticmethod
    def d():
      s = sys.stdin.readline().rstrip()
      print('First' if len(s)&1^(s[0]==s[-1]) else 'Second')


  class ABC049:
    @staticmethod
    def a():
      vowels = set('aeiou')
      print('vowel' if sys.stdin.readline().rstrip() in vowels else 'consonant')

    @staticmethod
    def b():
      h, w, *s = sys.stdin.read().split()
      for l in s:
        for _ in range(2): print(l)

    @staticmethod
    def c():
      t = set('dream, dreamer, erase, eraser'.split(', '))
      def obtainable(s):
        while True:
          for i in range(5, 8):
            if s[-i:] in t:
              s = s[:-i]
              if not s: return True
              break
          else: return False

      s = sys.stdin.readline().rstrip()
      print('YES' if obtainable(s) else 'NO')

    @staticmethod
    def d():
      n, k, l = map(int, sys.stdin.readline().split())
      uf1 = GeometryTopology.Graph(n); uf1.init_dsu()
      uf2 = GeometryTopology.Graph(n); uf2.init_dsu()

      def add_edges(uf, m):
        for _ in range(m):
          x, y = map(int, sys.stdin.readline().split())
          x -= 1; y -= 1
          uf.unite(x, y)

      add_edges(uf1, k); add_edges(uf2, l)

      g = defaultdict(list)
      for i in range(n): g[(uf1.find(i), uf2.find(i))].append(i)

      res = [None] * n
      for a in g:
        for i in g[a]: res[i] = len(g[a])

      print(*res, sep=' ')


  class ABC050:
    @staticmethod
    def a():
      print(eval(sys.stdin.readline().rstrip()))

    @staticmethod
    def b():
      n = int(sys.stdin.readline().rstrip())
      t = np.array(sys.stdin.readline().split(), dtype=np.int64)
      m, *px = map(int, sys.stdin.read().split())
      p, x = np.array(px).reshape(m, 2).T; p -= 1
      print(*(t.sum()+x-t[p]), sep='\n')

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = Counter(a)
      if n&1 and not(a[0]==1 and all(a[i]==2 for i in range(2, n, 2))):
        print(0); return
      if ~n&1 and any(a[i]!= 2 for i in range(1, n, 2)):
        print(0); return
      print(pow(2, n//2, MOD))

    @staticmethod
    def d(): pass


  class ABC051:
    @staticmethod
    def a():
      print(' '.join(sys.stdin.readline().rstrip().split(',')))

    @staticmethod
    def b():
      k, s = map(int, sys.stdin.readline().split())
      tot = 0
      for x in range(k+1):
        if s-x < 0: break
        if s-x > 2*k: continue
        tot += s-x+1 if s-x<=k else 2*k-(s-x)+1
      print(tot)

    @staticmethod
    def c():
      x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
      dx, dy = x2-x1, y2-y1
      print('U'*dy+'R'*(dx+1)+'D'*(dy+1)+'L'*(dx+1)+'U'+'L'+'U'*(dy+1)+'R'*(dx+1)+'D'*(dy+1)+'L'*dx)

    @staticmethod
    def d():
      n, m, *abc = map(int, sys.stdin.read().split())
      x = np.arange(n)
      a, b, c = np.array(abc).reshape(m, 3).T; a -= 1; b -= 1
      d = shortest_path(csr_matrix((c, (a, b)), shape=(n, n)), method='FW', directed=False).astype(np.int64)
      print(m-np.any(d[x,a[:,None]]+c[:,None]==d[x,b[:,None]], axis=1).sum())


  class ABC052:
    @staticmethod
    def a():
      a, b, c, d = map(int, sys.stdin.readline().split())
      print(max(a*b, c*d))

    @staticmethod
    def b():
      n, s = sys.stdin.read().split()
      n = int(n)
      a = [0] * (n+1)
      for i in range(n):
        a[i+1] = a[i] + (1 if s[i]=='I' else -1)
      print(max(a))

    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())
      pn = NumberTheory.PrimeNumbers(n)
      s = 1
      for c in pn.factorize_factorial(n).values():
        s = s*(c+1)%MOD
      print(s)

    @staticmethod
    def d():
      n, a, b, *x = map(int, sys.stdin.read().split())
      x = np.array(x)
      print(np.minimum((x[1:]-x[:-1])*a, b).sum())

  class ABC053:
    @staticmethod
    def a():
      print('ABC' if int(sys.stdin.readline().rstrip())<1200 else 'ARC')

    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      print(len(s)-s.find('A')-s[::-1].find('Z'))

    @staticmethod
    def c():
      x = int(sys.stdin.readline().rstrip())
      q, r = divmod(x, 11)
      print(2*q + (r+5)//6)

    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      print(n-((n-len(set(a))+1)//2*2))

  class ABC054:
    @staticmethod
    def a():
      def f(x):
        return (x+11)%13
      a, b = map(int, sys.stdin.readline().split())
      print('Alice' if f(a)>f(b) else 'Bob' if f(a)<f(b) else 'Draw')

    @staticmethod
    def b():
      n, m = map(int, sys.stdin.readline().split())
      a = [sys.stdin.readline().rstrip() for _ in range(n)]
      b = [sys.stdin.readline().rstrip() for _ in range(m)]

      for i in range(n-m+1):
        for j in range(n-m+1):
          for y in range(m):
            for x in range(m):
              if a[i+y][j+x]==b[y][x]: continue
              break
            else: continue
            break
          else: print('Yes'); return
      print('No')

    @staticmethod
    def c():
      n, m, *ab = map(int, sys.stdin.read().split())
      g = GeometryTopology.Graph(n)
      for a, b in zip(*[iter(ab)]*2):
        a -= 1; b -= 1
        g.add_edge(a,b)
        g.add_edge(b,a)

      cnt = 0
      stack = [(0, 1)]
      while stack:
        u, s = stack.pop()
        if s==(1<<n)-1: cnt+=1; continue
        for v in g.edges[u]:
          if s>>v&1: continue
          stack.append((v, s|1<<v))
      print(cnt)

    @staticmethod
    def d():
      n, ma, mb, *abc = map(int, sys.stdin.read().split())
      dp = np.full((401, 401), np.inf); dp[0,0] = 0
      for a, b, c in zip(*[iter(abc)]*3):
        np.minimum(dp[a:, b:], dp[:-a, :-b]+c, out=dp[a:, b:])
      i = np.arange(1, 400//max(ma,mb)+1)
      res = dp[i*ma, i*mb].min()
      print(int(res) if res != np.inf else -1)


  class ABC055:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      print(800*n - 200*(n//15))

    @staticmethod
    def b():
      n = int(sys.stdin.readline().rstrip())
      fac, _ = Algebra.generate_fac_ifac(n, MOD)
      print(fac[-1])

    @staticmethod
    def c():
      n, m = map(int, sys.stdin.readline().split())
      print(m//2 if m<=2*n else n+(m-2*n)//4)

    @staticmethod
    def d():
      n, s = sys.stdin.read().split(); n = int(n)
      s = [1 if c=='o' else 0 for c in s]
      def possible(t):
        for i in range(1, n-1): t[i+1] = t[i-1]^t[i]^s[i]
        return ((t[0]^s[0]^t[1]^t[-1])|(t[-1]^s[-1]^t[-2]^t[0]))^1

      for fst in [(1,0), (0,1), (1,1), (0,0)]:
        t = [None]*n; t[0], t[1] = fst[0], fst[1]
        if possible(t): print(''.join('S' if x==1 else 'W' for x in t)); return
      print(-1)


  class ABC056:
    @staticmethod
    def a():
      def to_i(c):
        return 1 if c=='H' else 0
      a, b = map(to_i, sys.stdin.readline().split())
      print('D' if a^b else 'H')

    @staticmethod
    def b():
      w, a, b = map(int, sys.stdin.readline().split())
      if a>b: a,b = b,a
      print(max(b-(a+w), 0))

    @staticmethod
    def c():
      x = int(sys.stdin.readline().rstrip())
      print(int(math.ceil(math.sqrt(2*x+1/4)-.5)))


    @staticmethod
    def d():
      n, k, *a = map(int, sys.stdin.read().split())
      a = sorted(min(x,k) for x in a)

      def necessary(i):
        dp = np.zeros(k, dtype=np.bool); dp[0] = True
        for j in range(n):
          if j==i: continue
          dp[a[j]:] += dp[:-a[j]]
        return np.any(dp[k-a[i]:])

      def binary_search():
        lo, hi = -1, n
        while hi-lo > 1:
          i = (lo+hi)//2
          if necessary(i): hi = i
          else: lo = i
        return hi

      print(binary_search())



  class ABC057:
    @staticmethod
    def a():
      a, b = map(int, sys.stdin.readline().split())
      print((a+b)%24)

    @staticmethod
    def b():
      n, m, *I = map(int, sys.stdin.read().split())
      I = np.array(I).reshape(-1, 2)
      ab, cd = I[:n], I[n:]
      print(*(np.argmin(np.absolute(ab[:,None]-cd).sum(axis=-1), axis=-1)+1), sep='\n')

    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())
      divs = NumberTheory.find_divisors(n)
      print(len(str(divs[bi_l(divs, math.sqrt(n))])))


    @staticmethod
    def d():
      c = Combinatorics.choose
      n, a, b, *v = map(int, sys.stdin.read().split())
      v.sort()
      print(sum(v[-a:])/a)
      l, r = bi_l(v, v[-a]), bi_r(v, v[-a])
      print(sum(c(r-l, i) for i in range(r-n+a, r-max(l,n-b)+1)) if r==n else c(r-l, r-n+a))


  class ABC058:
    @staticmethod
    def a():
      a, b, c = map(int, sys.stdin.readline().split())
      print('YES' if c-b==b-a else 'NO')

    @staticmethod
    def b():
      s, t = sys.stdin.read().split()
      a = ''
      for i in range(len(t)): a += s[i]+t[i]
      if len(s)>len(t): a += s[-1]
      print(a)

    @staticmethod
    def c():
      n, *s = sys.stdin.read().split()
      res = {c: 100 for c in string.ascii_lowercase}
      for counter in map(Counter, s):
        for c, x, in res.items(): res[c] = min(x, counter[c])
      t = ''
      for c, x in sorted(res.items()): t += c*x
      print(t)

    @staticmethod
    def d():
      n, m, *xy = map(int, sys.stdin.read().split())
      x, y = np.array(xy[:n]), np.array(xy[n:])
      print((x*(np.arange(n)+1)-np.cumsum(x)).sum()%MOD*((y*(np.arange(m)+1)-np.cumsum(y)).sum()%MOD)%MOD)

  class ABC059:
    @staticmethod
    def a():
      def initial(s): return s[0].upper()
      print(''.join(map(initial, sys.stdin.readline().split())))


    @staticmethod
    def b():
      a, b = sys.stdin.read().split()
      la, lb = len(a), len(b)
      print('GREATER' if la>lb else 'LESS' if la<lb else 'GREATER' if a>b else 'LESS' if a<b else 'EQUAL')

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      c = s = 0
      for i in range(n):
        s += a[i]
        if i&1 and s>=0: c += s+1; s=-1
        elif i&1^1 and s<=0: c += 1-s; s=1
      c1 = c
      c = s = 0
      for i in range(n):
        s += a[i]
        if i&1 and s<=0: c += 1-s; s=1
        elif i&1^1 and s>=0: c += s+1; s=-1
      c2 = c
      print(min(c1, c2))


    @staticmethod
    def d():
      x, y = map(int, sys.stdin.readline().split())
      print('Brown' if abs(x-y)<=1 else 'Alice')


  class ABC060:
    @staticmethod
    def a():
      a, b, c = sys.stdin.readline().split()
      print('YES' if a[-1]==b[0] and b[-1]==c[0] else 'NO')

    @staticmethod
    def b():
      a, b, c = map(int, sys.stdin.readline().split())
      print('NO' if c%NumberTheory.gcd(a,b) else 'YES')


    @staticmethod
    def c():
      n, t, *a = map(int, sys.stdin.read().split())
      print(sum(min(a[i+1]-a[i], t) for i in range(n-1))+t)


    @staticmethod
    def d():
      n, W, *wv = map(int, sys.stdin.read().split())
      v, w0 = [[] for _ in range(4)], wv[0]
      for a, b in zip(*[iter(wv)]*2): v[a-w0].append(b)
      for i in range(4):
        v[i] = (sorted(v[i])+[0])[::-1]
        *v[i], = itertools.accumulate(v[i])
      global res; res = 0
      @lru_cache(maxsize=None)
      def dfs(i,j,k):
        if i>=len(v[0]) or j>=len(v[1]) or k>=len(v[2]): return
        w = j+2*k + (i+j+k)*w0
        if w > W: return
        l = min(len(v[3])-1, (W-w)//(w0+3))
        global res; res = max(res, v[0][i]+v[1][j]+v[2][k]+v[3][l])
        dfs(i+1,j,k); dfs(i,j+1,k); dfs(i,j,k+1)
      dfs(0,0,0)
      print(res)

  class ABC061:
    @staticmethod
    def a():
      a, b, c = map(int, sys.stdin.readline().split())
      print('Yes' if a <= c <= b else 'No')

    @staticmethod
    def b():
      n, m, *ab = map(int, sys.stdin.read().split())
      ab = np.array(ab) - 1
      g = np.zeros(n, dtype=np.int32)
      np.add.at(g, ab, 1)
      print(*g, sep='\n')


    @staticmethod
    def c():
      n, k, *ab = map(int, sys.stdin.read().split())
      ab = np.transpose(np.array(ab).reshape(n,2))
      a, b = ab[:, np.argsort(ab[0])]
      print(a[np.cumsum(b)>=k][0])

    @staticmethod
    def d():
      n, m, *abc = map(int, sys.stdin.read().split())
      a, b, c = np.array(abc).reshape(m, 3).T; a -= 1; b -= 1; c *= -1
      g = csr_matrix(([1]*(m+1), (np.append(a, n-1), np.append(b, 0))), (n, n))
      _, labels = connected_components(g, connection='strong')
      bl = (labels[a]==labels[0]) & (labels[b]==labels[0])
      g = csr_matrix((c[bl], (a[bl], b[bl])), (n, n))
      try: print(-shortest_path(g, method='BF', directed=True, indices=0)[-1].astype(int))
      except: print('inf')

    @staticmethod
    def d_2():
      n, m, *abc = map(int, sys.stdin.read().split())
      a, b, c = np.array(abc).reshape(m, 3).T; a -= 1; b -= 1; c *= -1
      d = np.full(n, np.inf); d[0] = 0
      for _ in range(n-1): np.minimum.at(d, b, d[a]+c)
      neg_cycle = np.zeros(n, dtype=np.bool)
      for _ in range(n):
        np.logical_or.at(neg_cycle, b, d[a]+c<d[b])
        np.minimum.at(d, b, d[a]+c)
      print(inf if neg_cycle[-1] else -d[-1].astype(int))


  class ABC062:
    @staticmethod
    def a():
      g = [0, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0]
      x, y = map(int, sys.stdin.readline().split())
      print('Yes' if g[x-1]==g[y-1] else 'No')

    @staticmethod
    def b():
      h, w = map(int, sys.stdin.readline().split())
      a = np.array([list(s) for s in sys.stdin.read().split()], dtype='U1')
      a = np.pad(a, pad_width=1, constant_values='#')
      for s in a: print(''.join(s))

    @staticmethod
    def c():
      h, w = map(int, sys.stdin.readline().split())
      if h*w%3==0: print(0); return
      def minimize(h, w):
        return min(h, *(s[-1]-s[0] for x in range(w//3, w//3+2) for s in (sorted([h*x, h//2*(w-x), (h+1)//2*(w-x)]),)))

      print(min(minimize(h,w), minimize(w,h)))


    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)

      def optimize(a):
        a = list(a)
        l, r = a[:n], a[n:]; heapify(l)
        s = [None]*(n+1); s[0] = sum(l)
        for i in range(n):
          x = heappop(l)
          heappush(l, max(x, r[i]))
          s[i+1] = s[i]+max(0, r[i]-x)
        return np.array(s)

      print((optimize(a[:2*n]) + optimize(-a[-1:n-1:-1])[::-1]).max())

  class ABC063:
    @staticmethod
    def a():
      a = sum(map(int, sys.stdin.readline().split()))
      print('error' if a>=10 else a)


    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      print('yes' if len(set(s))==len(s) else 'no')

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      s = a.sum()
      if s%10: print(s)
      elif not np.count_nonzero(a%10): print(0)
      else: print(s-a[a%10!=0].min())



    @staticmethod
    def d():
      n, a, b, *h = map(int, sys.stdin.read().split())
      h = np.array(h)
      d = a-b

      def possible(c):
        hh = h.copy()
        np.maximum(hh-b*c, 0, out=hh)
        return ((hh+d-1)//d).sum() <= c

      def binary_search():
        lo, hi = 0, 10**9
        while hi-lo > 1:
          c = (lo+hi)//2
          if possible(c): hi = c
          else: lo = c
        return hi

      print(binary_search())

  class ABC064:
    @staticmethod
    def a():
      r, g, b = map(int, sys.stdin.readline().split())
      print('NO' if (10*g+b)%4 else 'YES')

    @staticmethod
    def b():
      n, *a = map(int, sys.stdin.read().split())
      a.sort()
      print(a[-1]-a[0])

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = np.bincount(np.minimum(np.array(a)//400, 8), minlength=9)
      mx = np.count_nonzero(a[:-1]) + a[-1]
      mn = max(mx-a[-1], 1)
      print(mn, mx)

    @staticmethod
    def d():
      n, s = sys.stdin.read().split()
      l = r = 0
      for c in s:
        if c=='(': r += 1
        else:
          if r==0: l += 1
          else: r -= 1
      print('('*l+s+')'*r)

  class ABC065:
    @staticmethod
    def a():
      x, a, b = map(int, sys.stdin.readline().split())
      y = -a+b
      print('delicious' if y<=0 else 'safe' if y<=x else 'dangerous')

    @staticmethod
    def b():
      n, *a = [int(x)-1 for x in sys.stdin.read().split()]
      i = 0
      for c in range(n):
        i = a[i]
        if i == 1: print(c+1); return
      print(-1)

    @staticmethod
    def c():
      n, m = map(int, sys.stdin.readline().split())
      d = abs(n-m)
      if d >= 2: print(0); return
      fac, _ = Algebra.generate_fac_ifac(10**5)
      print(fac[n]*fac[m]*(1 if d else 2)%MOD)

    @staticmethod
    def d():
      n, *xy = map(int, sys.stdin.read().split())
      x, y = np.array(xy).reshape(n,2).T
      i = np.argsort(x); ax, bx, cx = i[:-1], i[1:], x[i[1:],]-x[i[:-1]]
      i = np.argsort(y); ay, by, cy = i[:-1], i[1:], y[i[1:],]-y[i[:-1]]
      e = np.vstack([np.hstack([ax,ay]),np.hstack([bx,by]),np.hstack([cx,cy])])
      e = e[:,np.argsort(e[-1])]
      _, i = np.unique(e[:-1], return_index=True, axis=1)
      a, b, c = e[:,i]
      print(minimum_spanning_tree(csr_matrix((c,(a,b)), (n,n))).astype(np.int64).sum())


    @staticmethod
    def d_2():
      n, *xy = map(int, sys.stdin.read().split())
      x, y = xy[::2], xy[1::2]
      g = GeometryTopology.Graph(n)
      def make(a):
        b = sorted(enumerate(a), key=lambda x: x[1])
        for i in range(n-1):
          u, v, w = b[i][0], b[i+1][0], b[i+1][1]-b[i][1]
          for u, v in [(v,u), (u,v)]:
            if not v in g.edges[u]: g.add_edge(u, v, weight=w)
            else: g.edges[u][v].weight = min(g.edges[u][v].weight, w)
      make(x); make(y)
      _, d = g.kruskal()
      # _, d = g.prim()
      # _, d = g.boruvka()
      print(d)



  class ABC066:
    @staticmethod
    def a():
      print(sum(sorted(map(int, sys.stdin.readline().split()))[:-1]))

    @staticmethod
    def b():
      s = sys.stdin.readline().rstrip()
      def f(s):
        n = len(s)//2
        return s[:n] == s[n:]
      for i in range(len(s)-2, 0, -2):
        if f(s[:i]): print(i); return

    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      b = deque()
      for i in range(n):
        if i&1: b.appendleft(a[i])
        else: b.append(a[i])
      if n&1: b.reverse()
      print(*b)

    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      tmp = [None]*(n+1)
      for i in range(n+1):
        if tmp[a[i]] is not None: d=tmp[a[i]]+n-i; break
        tmp[a[i]] = i
      k = np.arange(1, n+2)
      c = Combinatorics.CombinationsMod(n+1, MOD)
      print(*((c(n+1,k)-c(d,k-1))%MOD), sep='\n')


  class ABC067:
    @staticmethod
    def a():
      a, b = map(int, sys.stdin.readline().split())
      print('Impossible' if a%3 and b%3 and (a+b)%3 else 'Possible')

    @staticmethod
    def b():
      n, k, *l = map(int, sys.stdin.read().split())
      print(sum(sorted(l)[-k:]))


    @staticmethod
    def c():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      np.cumsum(a, out=a)
      print(np.absolute(a[-1]-2*a[:-1]).min())


    @staticmethod
    def d():
      n, *ab = map(int, sys.stdin.read().split())
      g = GeometryTopology.Graph(n)
      for a, b in zip(*[iter(ab)]*2):
        a -= 1; b -= 1
        g.add_edge(a, b); g.add_edge(b,a)
      d1, d2 = g.bfs(0), g.bfs(n-1)
      print('Fennec' if sum(d1[i]<=d2[i] for i in range(n)) > n//2 else 'Snuke')

  class ABC068:
    @staticmethod
    def a():
      print('ABC'+sys.stdin.readline().rstrip())

    @staticmethod
    def b():
      print(2**math.floor(math.log2(int(sys.stdin.readline().rstrip()))))

    @staticmethod
    def c():
      n, m, *ab = map(int, sys.stdin.read().split())
      a, b = np.array(ab).reshape(m, 2).T
      d = shortest_path(csr_matrix(([1]*m, (a-1, b-1)), (n,n)), method='D', directed=False, indices=0).astype(np.int32)
      print('POSSIBLE' if d[-1]==2 else 'IMPOSSIBLE')

    @staticmethod
    def d():
      k = int(sys.stdin.readline().rstrip())
      n = 50; print(n)
      q,r = divmod(k,n); a = np.arange(n-1,-1,-1)+q; a[:r]+=1; print(*a)

  class ABC069:
    @staticmethod
    def a():
      n, m = map(int, sys.stdin.readline().split())
      print((n-1)*(m-1))


    @staticmethod
    def b():
      pass

    @staticmethod
    def c():
      pass


    @staticmethod
    def d():
      h, w, n, *a = map(int, sys.stdin.read().split())
      c = [i+1 for i in range(n) for j in range(a[i])]
      for i in range(h):
        row = c[i*w:(i+1)*w]
        if i&1: row = row[::-1]
        print(*row)

  class ABC070:
    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      g = GeometryTopology.Graph(n)
      for _ in range(n-1):
        a, b, c = map(int, sys.stdin.readline().split()); a-=1; b-=1
        g.add_edge(a, b, weight=c); g.add_edge(b, a, weight=c)
      q, k = map(int, sys.stdin.readline().split())
      d = g.bfs(k-1)
      for _ in range(q):
        x, y = map(int, sys.stdin.readline().split()); x-=1; y-=1
        print(d[x]+d[y])

  class ABC071:
    @staticmethod
    def d():
      n, *s = sys.stdin.read().split(); n = int(n)
      s = list(zip(*s))
      dp = [0]*n; dp[0] = 3 if s[0][0]==s[0][1] else 6
      for i in range(1,n):
        dp[i] = dp[i-1]
        if s[i][0]==s[i-1][0]: continue
        dp[i] *= 2 if s[i-1][0]==s[i-1][1] else 3 if s[i][0]!=s[i][1] else 1
        dp[i] %= MOD
      print(dp[-1])

  class ABC072:
    @staticmethod
    def d():
      n, *p = map(int, sys.stdin.read().split())
      p += [-1]
      cnt, i = 0, 0
      while i < n:
        if p[i]==i+1:
          cnt += p[i]==i+1
          if p[i+1]==i+2: i += 1
        i += 1
      print(cnt)


  class ABC073:
    @staticmethod
    def a():
      pass

    @staticmethod
    def b():
      pass

    @staticmethod
    def c():
      pass

    @staticmethod
    def d():
      n, m, r, *I = map(int, sys.stdin.read().split())
      I = np.array(I)
      a, b, c = I[r:].reshape(m,3).T
      d = shortest_path(csr_matrix((c, (a-1, b-1)), (n,n)), method='FW', directed=False).astype(np.int32)
      r = np.array([*itertools.permutations(I[:r]-1)])
      print((d[r[:,:-1], r[:,1:]].sum(axis=1)).min())

  class ABC074:
    @staticmethod
    def a():
      pass

    @staticmethod
    def b():
      pass

    @staticmethod
    def c():
      pass

    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a, dtype=np.int32).reshape(n,n)
      b = shortest_path(a, method='FW').astype(np.int32)
      if (b < a).any(): print(-1); return
      np.fill_diagonal(b, 10**9)
      a[np.any(b[:,None]+b<=a[:,:,None], axis=2)] = 0
      print(a.sum()//2)



  class ABC075:
    @staticmethod
    def a():
      pass

    @staticmethod
    def b():
      pass

    @staticmethod
    def c():
      pass

    @staticmethod
    def d():
      n, k, *xy = map(int, sys.stdin.read().split())
      xy = np.array(xy).reshape(n,2)
      x_y = xy.copy()[np.argsort(xy[:,0])]
      y_x = xy.copy()[np.argsort(xy[:,1])]
      comb = np.array([*itertools.combinations(range(n),2)])
      i1, i2 = comb.T
      j1, j2 = comb[None,:].T
      s = (y_x[:,1][i2]-y_x[:,1][i1]) * (x_y[:,0][j2]-x_y[:,0][j1])
      c = np.zeros((n+1,n+1), dtype=np.int64)
      for i in range(n): c[i+1, 1:] += c[i, 1:] + (y_x[i,0]<=x_y[:,0])
      a = c[i2+1, j2+1] - c[i2+1, j1] - c[i1, j2+1] + c[i1, j1]
      print(s[a>=k].min())


  class ABC076:
    @staticmethod
    def d():
      n, *tv = map(int, sys.stdin.read().split())
      t, v = np.array(tv).reshape(2, n)
      t = np.pad(t, pad_width=[2,1], constant_values=0)
      np.cumsum(t, out=t)
      l, r = t[:-1], t[1:]
      v = np.pad(v, pad_width=[1,1], constant_values=0)
      x = np.arange(0, r[-1]+0.1, 0.5, dtype=np.float32)[:,None]
      # y = np.stack([v-(x-l), np.zeros(r[-1]*2+1, dtype=np.float32)[:,None]+v, v+(x-r)]).max(axis=0).min(axis=1)
      mx = v-(x-l); np.maximum(mx, v, out=mx); np.maximum(mx, v+(x-r), out=mx)
      y = mx.min(axis=1)
      print(((y[:-1]+y[1:])/4).sum())


  class ABC077:
    @staticmethod
    def d():
      k = int(sys.stdin.readline().rstrip())
      g = GeometryTopology.Graph(k)
      for i in range(k):
        g.add_edge(i, i*10%k, weight=0)
        g.add_edge(i, (i+1)%k, update=False, weight=1)
      print(1+g.bfs01(1)[0])


  class ABC078:
    @staticmethod
    def d():
      n, z, w, *a = map(int, sys.stdin.read().split())
      print(abs(a[0]-w) if n==1 else max(abs(a[-1]-w), abs(a[-1]-a[-2])))

  class ABC079:
    @staticmethod
    def d():
      h, w, *I = map(int, sys.stdin.read().split())
      I = np.array(I)
      c = I[:100].reshape(10,10)
      a = I[100:].reshape(h,w)
      c = shortest_path(c.T, method='D', indices=1).astype(np.int32)
      print(c[a[a!=-1]].sum())

  class ABC080:
    @staticmethod
    def d():
      n, c, *stc = map(int, sys.stdin.read().split())
      using = np.zeros((c, 10**5+2), dtype=np.int8)
      s, t, c = np.array(stc).reshape(n,3).T
      np.add.at(using, (c-1, s), 1)
      np.subtract.at(using, (c-1, t+1), 1)
      np.cumsum(using, axis=1, out=using)
      print(np.count_nonzero(using, axis=0).max())

  class ABC081:
    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      i = np.argmax(np.absolute(a))
      print(2*n-1)
      for j in range(n): print(i+1, j+1)
      if a[i] >= 0:
        for j in range(n-1): print(j+1, j+2)
      else:
        for j in range(n-1, 0, -1): print(j+1, j)


  class ABC082:
    @staticmethod
    def d():
      s = [1 if c=='T' else 0 for c in sys.stdin.readline().rstrip()] + [1]
      x, y = map(int, sys.stdin.readline().split())
      i = j = 0
      while s[i]==0: x -= 1; i +=1
      d = [[], []]
      while i < len(s):
        if s[i]: j ^= 1; i += 1; continue
        c = 0
        while s[i]==0: c += 1; i += 1
        d[j].append(c)

      def possible(a, s):
        dp = np.zeros(sum(a)+1, dtype=np.bool)
        if s >= len(dp): return False
        dp[-1] = True
        for x in a: dp[:-2*x] += dp[2*x:]
        return dp[s]

      print('Yes' if possible(d[0], abs(x)) & possible(d[1], abs(y)) else 'No')


  class ABC083:
    @staticmethod
    def d():
      s = np.array(list(sys.stdin.readline().rstrip()), dtype=np.int8)
      k = np.argwhere(s[:-1] != s[1:]).ravel()
      if not k.size: print(len(s)); return
      print(np.maximum(k+1, len(s)-1-k).min())


  class ABC084:
    @staticmethod
    def d():
      pn = NumberTheory.PrimeNumbers()
      n = np.arange(10**5+1)
      cnt = (pn.is_prime[n] & pn.is_prime[(n+1)//2]).astype(np.int32)
      np.cumsum(cnt, out=cnt)
      q, *lr = map(int, sys.stdin.read().split())
      l, r = np.array(lr).reshape(q, 2).T
      print(*(cnt[r]-cnt[l-1]), sep='\n')


  class ABC085:
    @staticmethod
    def d():
      n, h, *ab = map(int, sys.stdin.read().split())
      a, b = np.array(ab).reshape(n, 2).T
      a = np.sort(a)[-1]; b = np.sort(b[b>=a])[::-1]
      np.cumsum(b, out=b)
      print(np.searchsorted(b, h, side='left')+1 if h<=b[-1] else len(b)+(h-b[-1]+a-1)//a)

  class ABC086:
    @staticmethod
    def d():
      n, k = map(int, sys.stdin.readline().split())
      xy = []
      for _ in range(n):
        a, b, c = sys.stdin.readline().split()
        a, b = int(a), int(b)
        b += k*(c=='W')
        xy.append((a,b))
      x, y = np.array(xy, dtype=np.int32).T % (2*k)
      s = np.zeros((3*k, 3*k), dtype=np.int32)
      np.add.at(s, (y,x), 1); np.add.at(s, (y+k, x+k), 1); np.add.at(s, (y+k, x), -1); np.add.at(s, (y, x+k), -1)
      del x; del y
      s = s.cumsum(axis=0).cumsum(axis=1)
      s[:k] += s[-k:]; s[:, :k] += s[:, -k:]; s = s[:-k, :-k]
      s[:k, :k] += s[-k:, -k:]; s[:k, -k:] += s[-k:, :k]; s = s[:k]
      print(s.max())

  class ABC087:
    @staticmethod
    def d():
      n, m, *lrd = map(int, sys.stdin.read().split())
      g = GeometryTopology.Graph(n)
      for l, r, d in zip(*[iter(lrd)]*3):
        l -= 1; r -= 1
        g.add_edge(l, r, weight=d); g.add_edge(r, l, weight=-d)

      x = [None] * n
      @lru_cache(maxsize=None)
      def dfs(u, y):
        if x[u] is not None:
          if x[u] != y: raise Exception('conflict!')
          return
        x[u] = y
        for v, e in g.edges[u].items(): dfs(v, y+e.weight)

      for u in range(n):
        if x[u] is not None: continue
        # try: dfs(u, 0)
        # except: print('No'); return
        stack = [(u, 0)]
        while stack:
          u, y = stack.pop()
          if x[u] is not None:
            if x[u] != y: print('No'); return
            continue
          x[u] = y
          for v, e in g.edges[u].items(): stack.append((v, y+e.weight))
      print('Yes')

  class ABC088:
    @staticmethod
    def d():
      h, w = map(int, sys.stdin.readline().split())
      s = ''.join(sys.stdin.read().split())
      g = GeometryTopology.Graph(h*w)
      cnt = h*w
      for u in range(h*w):
        if s[u] == '#': cnt -= 1; continue
        i, j = divmod(u, w)
        if i>0 and s[u-w]=='.': g.add_edge(u, u-w, weight=1)
        if i<h-1 and s[u+w]=='.': g.add_edge(u, u+w, weight=1)
        if j>0 and s[u-1]=='.': g.add_edge(u, u-1, weight=1)
        if j<w-1 and s[u+1]=='.': g.add_edge(u, u+1, weight=1)
      d = g.bfs(0)
      print(-1 if d[-1]==inf else cnt-d[-1]-1)

  class ABC089:
    @staticmethod
    def d():
      h, w, d, *I = map(int, sys.stdin.read().split())
      I = np.array(I)
      a = I[:h*w].reshape(h,w)
      l, r = I[h*w+1:].reshape(-1,2).T - 1
      yx = np.pad(np.argwhere(a)[np.argsort(a.ravel())], pad_width=[(0,d), (0,0)], constant_values=0)
      a = np.zeros(h*w+d, dtype=np.int32)
      for i in range(0, h*w-d, d):
        a[i+d:i+2*d] = a[i:i+d] + np.absolute(yx[i+d:i+2*d]-yx[i:i+d]).sum(axis=1)
      print(*(a[r]-a[l]), sep='\n')

  class ABC090:
    @staticmethod
    def d():
      n, k = map(int, sys.stdin.readline().split())
      b = np.arange(k+1, n+1)
      print((n//b*(b-k) + np.maximum(0, (n%b)-k+1*(k!=0))).sum())

  class ABC091:
    @staticmethod
    def d():
      n, *ab = map(int, sys.stdin.read().split())
      c = 2**np.arange(30)
      a, b = np.sort(np.array(ab).reshape(2,n)[:, None] % (2*c)[:,None])
      res = 0
      for i in range(30):
        j = np.searchsorted(b[i], np.arange(1, 5)[:,None]*c[i]-a[i]).sum(axis=1)
        j[1::2] *= -1
        res += (j.sum()&1) * c[i]
      print(res)

  class ABC092:
    @staticmethod
    def d():
      a, b = map(int, sys.stdin.readline().split())
      def make(color, cnt):
        g = [[color^1]*100 for _ in range(21)]
        for i in range(1, 21, 2):
          for j in range(0, 100, 2):
            if not cnt: return g
            g[i][j] = color; cnt -= 1
      g = make(0,a-1) + make(1,b-1)
      def convert(s): return ''.join('#' if c else '.' for c in s)
      print(42, 100)
      print(*map(convert, g), sep='\n')

  class ABC093:
    @staticmethod
    def d():
      q, *ab = map(int, sys.stdin.read().split())
      a, b = np.sort(np.array(ab).reshape(q,2)).T
      x = np.sqrt(a*b).astype(int)
      x[x*x==a*b] -= 1
      res = a-1
      res += (a-1) * (b-a<=1)
      res += (x+np.minimum(x-a-1*(x*(x+1)>=a*b), b-x-1)) * (b-a>=2)

      # res = 0
      # res += 2*(a-1) * (b-a<=1)
      # res += (2*x-1 - 1*(x*(x+1)>=a*b)) * (b-a >= 2)

      print(*res, sep='\n')



  class ABC094:
    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      a.sort()
      print(a[-1], end=' ')
      b = (a[-1]+1)//2
      i = bi_l(a, b)
      print(a[-2] if i==n-1 else a[i-1] if b-a[i-1]<=a[i]-b else a[i])



  class ABC095:
    @staticmethod
    def d():
      n, c, *xv = map(int, sys.stdin.read().split())

      def make(xv):
        x, v = xv.T
        s = np.cumsum(v)-x; rs = s-x
        np.maximum.accumulate(s, out=s)
        np.maximum.accumulate(rs, out=rs)
        return s, rs

      xv = np.pad(np.array(xv).reshape(n,2), pad_width=[(1,0), (0,0)], constant_values=0)
      ls, lrs = make(xv)
      xv[1:, 0] = c-xv[1:, 0]; xv[1:] = xv[-1:0:-1]
      rs, rrs = make(xv)
      print(np.maximum(ls+rrs[::-1], rs+lrs[::-1]).max())

  class ABC096:
    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      pn = NumberTheory.PrimeNumbers()
      a = [p for p in pn if p%5==1]
      print(*a[:n])


  class ABC097:
    @staticmethod
    def d():
      n, m = map(int, sys.stdin.readline().split())
      p = [int(x)-1 for x in sys.stdin.readline().split()]
      uf = GeometryTopology.Graph(n); uf.init_dsu()
      for x, y in zip(*[map(int, sys.stdin.read().split())]*2): uf.unite(x-1, y-1)
      groups = [set(p[u] for u in g) for g in uf.groups()]
      print(sum(i in groups[uf.find(i)] for i in range(n)))

  class ABC098:
    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      r = s = cnt = 0
      for l in range(n):
        while r<n and not(s&a[r]): s ^= a[r]; r += 1
        cnt += r-l; s ^= a[l]
      print(cnt)


  class ABC099:
    @staticmethod
    def d():
      n, c, *I = map(int, sys.stdin.read().split())
      I = np.array(I)
      d = I[:c*c].reshape(c,c)
      r = np.arange(n*n); r = (r//n + r%n)%3
      a = d[I[c*c:]-1, np.arange(c)[:,None]]
      r = np.arange(n*n); r = (r//n + r%n)%3 == np.arange(3)[:,None]
      a = np.vstack([a[:,r[i]].sum(axis=1) for i in range(3)])
      p = np.array([*itertools.permutations(range(c), 3)])
      print(a[np.arange(3),p].sum(axis=1).min())


  class ABC100:
    @staticmethod
    def d():
      n, m, *xyz = map(int, sys.stdin.read().split())
      xyz = np.array(xyz).reshape(n,3)
      op = np.array([*itertools.product((-1,1), repeat=3)])
      print(np.sort((op[:,None]*xyz).sum(axis=-1), axis=-1)[:,n-m:].sum(axis=-1).max())

  class ABC101:
    @staticmethod
    def d():
      def s(n): return sum(int(d) for d in str(n))
      def f(n):
        return sorted([pow(10,d)*(n//pow(10,d)+2)-1 for d in range(int(math.log10(n))+2)], key=lambda x: x/s(x))[0]
      k = int(sys.stdin.readline().rstrip())
      n = 1
      for _ in range(k): print(n); n = f(n)

  class ABC102:
    @staticmethod
    def d(): # two pointers (online)
      n, *a = map(int, sys.stdin.read().split())
      mn = inf
      i, k = 0, 2
      p,q,r,s = a[0], 0, a[1]+a[2], sum(a[3:])
      for j in range(1,n-2):
        q += a[j]; r -= a[j]
        while i < j-1:
          if abs(q-p-2*a[i+1]) <= abs(q-p):
            q -= a[i+1]; p += a[i+1]
            i += 1; continue
          break
        while k < n-2:
          if abs(s-r-2*a[k+1]) <= abs(s-r):
            s -= a[k+1]; r += a[k+1]
            k += 1; continue
          break
        tmp = sorted([p,q,r,s])
        mn = min(mn, tmp[-1]-tmp[0])
      print(mn)

    @staticmethod
    def d_2(): # binary_search (offline)
      n, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      def f(a):
        s = np.cumsum(a)
        i = np.searchsorted(s, s/2)
        l, r = s[i], s-s[i]
        bl = np.abs(r-l) > np.abs(r-l+2*a[i])
        l -= a[i]*bl; r += a[i]*bl
        return l, r
      (p,q), (s,r) = f(a), f(a[::-1])
      a = np.sort(np.vstack((p[:-1], q[:-1], r[-2::-1], s[-2::-1])), axis=0)[:,1:-1]
      print((a[-1]-a[0]).min())

  class ABC103:
    @staticmethod
    def d():
      n, m, *ab = map(int, sys.stdin.read().split())
      cnt = prev = 0
      for a, b in sorted(zip(*[iter(ab)]*2), key=lambda x: x[1]):
        a -= 1; b -= 1
        if a < prev: continue
        prev = b; cnt += 1
      print(cnt)

  class ABC104:
    @staticmethod
    def d():
      s = sys.stdin.readline().rstrip()[::-1]
      a = b = c = 0; d = 1
      for i in range(len(s)):
        if s[i]=='?': a,b,c,d = 3*a+b, 3*b+c, 3*c+d, 3*d
        elif s[i] == 'A': a += b
        elif s[i] == 'B': b += c
        elif s[i] == 'C': c += d
        a %= MOD; b %= MOD; c %= MOD; d %= MOD
      print(a)

  class ABC105:
    @staticmethod
    def d():
      n, m, *a = map(int, sys.stdin.read().split())
      s = r = cnt = 0
      for l in range(n):
        while r<n and (s+a[r])%m==0:
          s += a[r]; r += 1
        if s%m==0: cnt += r-l
        s -= a[l]
      print(cnt)

  class ABC106: pass
  class ABC107: pass
  class ABC108: pass
  class ABC109: pass
  class ABC110: pass
  class ABC111: pass
  class ABC112: pass
  class ABC113: pass
  class ABC114: pass
  class ABC115: pass
  class ABC116: pass
  class ABC117: pass
  class ABC118: pass
  class ABC119: pass
  class ABC120: pass
  class ABC121: pass
  class ABC122: pass
  class ABC123: pass
  class ABC124: pass
  class ABC125: pass
  class ABC126: pass
  class ABC127: pass
  class ABC128: pass
  class ABC129: pass
  class ABC130: pass
  class ABC131: pass
  class ABC132: pass
  class ABC133: pass
  class ABC134: pass
  class ABC135: pass
  class ABC136: pass
  class ABC137: pass
  class ABC138: pass
  class ABC139: pass
  class ABC140: pass
  class ABC141: pass
  class ABC142: pass
  class ABC143: pass
  class ABC144: pass
  class ABC145: pass
  class ABC146: pass
  class ABC147: pass
  class ABC148: pass
  class ABC149: pass
  class ABC150: pass
  class ABC151: pass
  class ABC152: pass
  class ABC153: pass
  class ABC154: pass
  class ABC155: pass
  class ABC156: pass
  class ABC157: pass
  class ABC158: pass
  class ABC159: pass
  class ABC160: pass
  class ABC161: pass
  class ABC162: pass
  class ABC163: pass
  class ABC164: pass
  class ABC165: pass
  class ABC166: pass
  class ABC167: pass
  class ABC168: pass
  class ABC169: pass

  class ABC170:
    @staticmethod
    def a():
      x = [int(x) for x in sys.stdin.readline().split()]
      for i in range(5):
        if x[i] != i+1:
          print(i+1)
          break

    @staticmethod
    def b():
      x, y = map(int, sys.stdin.readline().split())
      print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
    @staticmethod
    def c():
      x, n, *p = map(int, sys.stdin.read().split())
      a = list(set(range(102)) - set(p))
      a = [(abs(y-x), y) for y in a]
      print(sorted(a)[0][1])

    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      cand = set(a)
      cnt = 0
      for x, c in sorted(Counter(a).items()):
        cnt += c == 1 and x in cand
        cand -= set(range(x*2, 10**6+1, x))
      print(cnt)

    @staticmethod
    def e():
      n, q = map(int, sys.stdin.readline().split())
      queue = []
      m = 2*10**5
      infants = [[] for _ in range(m)]
      highest_rate = [None] * m
      where = [None] * n
      rate = [None] * n

      def entry(i, k):
        where[i] = k
        while infants[k]:
          r, j = heappop(infants[k])
          if where[j] != k or j == i: continue
          if rate[i] >= -r:
            highest_rate[k] = rate[i]
            heappush(queue, (rate[i], k, i))
          heappush(infants[k], (r, j))
          break
        else:
          highest_rate[k] = rate[i]
          heappush(queue, (rate[i], k, i))
        heappush(infants[k], (-rate[i], i))

      def transfer(i, k):
        now = where[i]
        while infants[now]:
          r, j = heappop(infants[now])
          if where[j] != now or j == i: continue
          if highest_rate[now] != -r:
            highest_rate[now] = -r
            heappush(queue, (-r, now, j))
          heappush(infants[now], (r, j))
          break
        else:
          highest_rate[now] = None
        entry(i, k)

      def inquire():
        while True:
          r, k, i = heappop(queue)
          if where[i] != k or r != highest_rate[k]: continue
          heappush(queue, (r, k, i))
          return r

      for i in range(n):
        a, b = map(int, sys.stdin.readline().split())
        rate[i] = a
        entry(i, b-1)
      for _ in range(q):
        c, d = map(int, sys.stdin.readline().split())
        transfer(c-1, d-1)
        print(inquire())



  class ABC171:
    @staticmethod
    def a():
      c = sys.stdin.readline().rstrip()
      print('A' if c < 'a' else 'a')

    @staticmethod
    def b():
      n, k, *p = map(int, sys.stdin.read().split())
      print(sum(sorted(p)[:k]))


    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())
      n -= 1
      l = 1
      while True:
        if n < pow(26, l):
          break
        n -= pow(26, l)
        l += 1
      res = ''.join([chr(ord('a')+d) for d in NumberTheory.base_convert(n, 26)][::-1])
      res = 'a'*(l-len(res)) + res
      print(res)

    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      a = [int(x) for x in sys.stdin.readline().split()]
      s = sum(a)
      cnt = Counter(a)
      q = int(sys.stdin.readline().rstrip())
      for _ in range(q):
        b, c = map(int, sys.stdin.readline().split())
        s += (c-b)*cnt[b]
        print(s)
        cnt[c] += cnt[b]; cnt[b] = 0

    @staticmethod
    def e():
      n, *a = map(int, sys.stdin.read().split())
      s = 0
      for x in a: s ^= x
      b = map(lambda x: x^s, a)
      print(*b, sep=' ')


  class ABC172:
    @staticmethod
    def a():
      a = int(sys.stdin.readline().rstrip()); print(a*(1+a+a**2))

    @staticmethod
    def b():
      s, t = sys.stdin.read().split(); print(sum(s[i]!=t[i] for i in range(len(s))))

    @staticmethod
    def c():
      n, m, k = map(int, sys.stdin.readline().split())
      a = [0] + [int(x) for x in sys.stdin.readline().split()]
      b = [int(x) for x in sys.stdin.readline().split()]
      *sa, = itertools.accumulate(a)
      *sb, = itertools.accumulate(b)
      res = 0
      for i in range(n+1):
        r = k - sa[i]
        if r < 0: break
        res = max(res, i+bi_r(sb, r))
      print(res)

    @staticmethod
    def d():
      n = int(sys.stdin.readline().rstrip())
      f = np.zeros(n+1, dtype=np.int64)
      for i in range(1, n+1):
        f[i::i] += 1
      print((np.arange(1, n+1)*f[1:]).sum())


  class ABC173:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      charge = (n+999)//1000 * 1000 - n
      print(charge)

    @staticmethod
    def b():
      n, *s = sys.stdin.read().split()
      c = Counter(s)
      for v in 'AC, WA, TLE, RE'.split(', '):
        print(f'{v} x {c[v]}')


    @staticmethod
    def c():
      h, w, k = map(int, sys.stdin.readline().split())
      c = [sys.stdin.readline().rstrip() for _ in range(h)]
      tot = 0
      for i in range(1<<h):
        for j in range(1<<w):
          cnt = 0
          for y in range(h):
            for x in range(w):
              if i>>y & 1 or j>>x & 1:
                continue
              cnt += c[y][x] ==  '#'
          tot += cnt == k
      print(tot)

    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      a.sort(reverse=True)
      res = a[0] + sum(a[1:1+(n-2)//2])*2 + a[1+(n-2)//2]*(n & 1)
      print(res)

    @staticmethod
    def e():
      MOD = 10**9+7
      n, k, *a = map(int, sys.stdin.read().split())
      minus = [x for x in a if x < 0]
      plus = [x for x in a if x > 0]
      if len(plus) + len(minus)//2*2 >= k: # plus
        *minus, = map(abs, minus)
        minus.sort(reverse=True)
        plus.sort(reverse=True)
        cand = []
        if len(minus)&1: minus = minus[:-1]
        for i in range(0, len(minus)-1, 2):
          cand.append(minus[i]*minus[i+1]%MOD)
        if k & 1:
          res = plus[0]
          plus = plus[1:]
        else:
          res = 1
        if len(plus)&1: plus = plus[:-1]
        for i in range(0, len(plus)-1, 2):
          cand.append(plus[i]*plus[i+1]%MOD)
        cand.sort(reverse=True)
        for x in cand[:k//2]:
          res *= x
          res %= MOD
        print(res)
      elif 0 in a:
        print(0)
      else:
        cand = sorted(map(abs, a))
        res = 1
        for i in range(k):
          res *= cand[i]
          res %= MOD
        res = MOD - res
        print(res)
        pass


  class ABC174:
    @staticmethod
    def a():
      print('Yes' if int(sys.stdin.readline().rstrip())>=30 else 'No')




  class ABC178:
    @staticmethod
    def a(): pass

    @staticmethod
    def b(): pass

    @staticmethod
    def c(): pass

    @staticmethod
    def d():
      s = int(sys.stdin.readline().rstrip())
      if s == 0: print(1); return
      elif s == 1: print(0); return
      c = np.eye(3, k=-1, dtype=np.int64)
      c[0, 0] = c[0, 2] = 1
      a = np.array([0, 0, 1])
      print(Algebra.dot(Algebra.matrix_pow(c, s-2), a)[0])

  class ABC179:
    @staticmethod
    def a():
      s = sys.stdin.readline().rstrip()
      print(s+'s' if s[-1]!='s' else s+'es')

    @staticmethod
    def b():
      n, *d = map(int, sys.stdin.read().split())
      d = np.array(d).reshape(n, 2).T
      d = np.equal(d[0], d[1]).astype(int)
      dd = d.copy()
      dd[1:] += d[:-1]
      dd[:-1] += d[1:]
      print('Yes' if (dd>=3).any() else 'No')



    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())
      res = (n//np.arange(1, n+1)).sum() - len(NumberTheory.find_divisors(n))
      print(res)


    @staticmethod
    def d():
      mod = 998244353
      n, k, *lr = map(int, sys.stdin.read().split())
      l, r = np.array(lr).reshape(k, -1).T
      @njit((i8, i8[:], i8[:]), cache=True)
      def solve(n, l, r):
        res = np.zeros(n*2, dtype=np.int64); res[0], res[1] = 1, -1
        for i in range(n-1):
          res[i+1] = (res[i+1]+res[i]) % mod
          res[i+l] = (res[i+l]+res[i]) % mod
          res[i+r+1] = (res[i+r+1]-res[i]) % mod
        print(res[n-1])
      solve(n, l, r)

    @staticmethod
    def e():
      n, x, m = map(int, sys.stdin.readline().split())
      res = [-1 for _ in range(m)]
      s = 0
      loop = np.zeros(m, dtype=np.int64)
      for i in range(m+1):
        if i==n: print(s); return
        if res[x] != -1:
          l, loop = i-res[x], loop[res[x]:i]
          q, r = divmod(n-i, l)
          print(s+q*loop.sum()+loop[:r].sum()); return
        res[x], loop[i] = i, x
        s += x; x = x**2 % m


  class ABC180:
    @staticmethod
    def a():
      n, a, b = map(int, sys.stdin.readline().split())
      print(n-a+b)

    @staticmethod
    def b():
      n, *x = map(int, sys.stdin.read().split())
      x = np.absolute(np.array(x))
      print(x.sum())
      print(np.sqrt((x**2).sum()))
      print(x.max())

    @staticmethod
    def c():
      n = int(sys.stdin.readline().rstrip())
      div = NumberTheory.find_divisors(n)
      print(*div, sep='\n')

    @staticmethod
    def d():
      x, y, a, b = map(int, sys.stdin.readline().split())
      cnt = 0
      while x*a <= x+b:
        x *= a
        if x >= y:
          print(cnt); return
        cnt += 1
      cnt += (y-x-1) // b
      print(cnt)

    @staticmethod
    def e():
      n, *xyz = map(int, sys.stdin.read().split())

      xyz = list(zip(*[iter(xyz)] * 3))
      dist = [[0] * n for _ in range(n)]
      for i in range(n):
        a, b, c = xyz[i]
        for j in range(n):
          p, q, r = xyz[j]
          dist[i][j] = abs(p-a) + abs(q-b) + max(0, r-c)

      dp = [[inf] * n for _ in range(1<<n)]
      dp[0][0] = 0
      for s in range(1<<n):
        for i in range(n):
          t = s|(1<<i)
          for j in range(n):
            dp[t][i] = min(dp[t][i], dp[s][j]+dist[j][i])
      print(dp[-1][0])



    @staticmethod
    def f(): # rewrite with jit compiling later.
      n, m, l = map(int, sys.stdin.readline().split())
      c = Combinatorics.CombinationsMod(n, MOD)
      path = np.zeros(n+1, dtype=np.int64); path[1] = path[2] = 1
      for i in range(3, n+1): path[i] = path[i-1]*i%MOD
      cycle = np.zeros(n+1, dtype=np.int64); cycle[1:] = path[:-1]
      dp = np.zeros((n+1, m+1), dtype=np.int64)
      def f(l):
        dp[:,:] = 0; dp[0,0] = 1
        for i in range(n):
          for j in range(m+1):
            k = np.arange(1, min(l, n-i, m-j+1)+1)
            dp[i+k, j+k-1] += dp[i, j]*c(n-i-1, k-1)%MOD*path[k]%MOD
            dp[i+k, j+k-1] %= MOD
            k = np.arange(2, min(l, n-i, m-j)+1)
            dp[i+k, j+k] += dp[i, j]*c(n-i-1, k-1)%MOD*cycle[k]%MOD
            dp[i+k, j+k] %= MOD
        return dp[n, m]

      print((f(l)-f(l-1))%MOD)

    @staticmethod
    def f_2(): # PyPy
      n, m, l = map(int, sys.stdin.readline().split())
      c = Combinatorics.CombinationsMod(n, MOD)
      path = [0] * (n+1); path[1] = path[2] = 1
      for i in range(3, n+1): path[i] = path[i-1]*i%MOD
      cycle = [0] + path[:-1]
      def f(l):
        dp = [[0]*(m+1) for _ in range(n+1)]; dp[0][0] = 1
        for i in range(n):
          for j in range(m+1):
            for k in range(1, min(l, n-i, m-j+1)+1):
              dp[i+k][j+k-1] += dp[i][j]*c(n-i-1, k-1)%MOD*path[k]%MOD
              dp[i+k][j+k-1] %= MOD
            for k in range(1, min(l, n-i, m-j)+1):
              dp[i+k][j+k] += dp[i][j]*c(n-i-1, k-1)%MOD*cycle[k]%MOD
              dp[i+k][j+k] %= MOD

        return dp[n][m]

      print((f(l)-f(l-1))%MOD)


  class ARC106:
    @staticmethod
    def a():
      n = int(sys.stdin.readline().rstrip())
      a = 1
      while pow(3,a)<=n:
        m, b = n-pow(3,a), 1
        while pow(5,b)<=m:
          if pow(5,b)==m: print(a, b); return
          b += 1
        a += 1
      print(-1)

    @staticmethod
    def b():
      n, m = map(int, sys.stdin.readline().split())
      a = [int(x) for x in sys.stdin.readline().split()]
      b = [int(x) for x in sys.stdin.readline().split()]
      uf = GeometryTopology.Graph(n); uf.init_dsu()
      for _ in range(m):
        c, d = map(int, sys.stdin.readline().split()); c -= 1; d -= 1
        uf.unite(c, d)
      ga, gb = [[] for _ in range(n)], [[] for _ in range(n)]
      for i in range(n):
        r = uf.find(i)
        ga[r].append(a[i]); gb[r].append(b[i])
      print('Yes' if all(sum(ga[i])==sum(gb[i]) for i in range(n)) else 'No')

    @staticmethod
    def c():
      n, m = map(int, sys.stdin.readline().split())
      if m < 0: print(-1); return
      if n == 1:
        if m != 0: print(-1); return
        print(1, 2); return
      if m >= n-1: print(-1); return
      l, r = 1, 10**9
      print(l, r)
      for _ in range(n-2-m):
        l += 1; r -= 1; print(l, r)
      r = l
      for _ in range(m+1):
        l, r = r+1, r+2
        print(l, r)

    @staticmethod
    def d():
      mod = 998244353
      n, k, *a = map(int, sys.stdin.read().split())
      a = np.array(a)
      b = np.zeros((k+1, n), dtype=np.int64)
      b[0] = 1
      for i in range(k): b[i+1] = b[i]*a%mod
      s = b.sum(axis=1) % mod
      inv_2 = pow(2, mod-2, mod)
      c = Combinatorics.CombinationsMod(mod=mod)
      for x in range(1, k+1):
        l = np.arange(x+1)
        print(((c(x, l)*s[l]%mod*s[l][::-1]%mod).sum()%mod - pow(2,x,mod)*s[x])%mod*inv_2%mod)

    @staticmethod
    def e():
      pass

    @staticmethod
    def f():
      pass


  class ARC107:
    @staticmethod
    def a():
      mod = 998244353
      a, b, c = map(int, sys.stdin.readline().split())
      s = (1+a)*a//2%mod * (1+b)*b//2%mod * (1+c)*c//2%mod
      print(s)

      pass
    @staticmethod
    def b():
      n, k = map(int, sys.stdin.readline().split())
      # e = a + b
      # f = c + d
      # 2 <= e,f <= 2*n
      # e + f = k,
      def c(m):
        if m <= n:
          return m - 1
        else:
          return 2*n - m + 1
      tot = 0
      for e in range(2, 2*n+1):
        f = e - k
        if f < 2 or f > 2*n: continue

        tot += c(e) * c(f)
      print(tot)


    @staticmethod
    def c():
      mod = 998244353
      n, k, *a = map(int, sys.stdin.read().split())
      a = np.array(a).reshape(n,n)
      uf1 = GeometryTopology.Graph(n); uf1.init_dsu()
      uf2 = GeometryTopology.Graph(n); uf2.init_dsu()
      for i in range(n-1):
        for j in range(i+1, n):
          if (a[i]+a[j] <= k).all():
            uf1.unite(i, j)
          if (a[:, i] + a[:, j] <= k).all():
            uf2.unite(i, j)

      fac, _ = Algebra.generate_fac_ifac(n=100, p=mod)
      g1 = uf1.groups()
      g2 = uf2.groups()
      y = 1
      for i in g1:
        l = len(i)
        if l == 0: continue
        y *= fac[l]
        y %= mod

      x = 1
      for i in g2:
        l = len(i)
        if l == 0: continue
        x *= fac[l]
        x %= mod
      print(x*y%mod)

    @staticmethod
    def d():
      mod = 998244353

      pass

    @staticmethod
    def e():
      pass

    @staticmethod
    def f():
      pass



  class ACL001:
    @staticmethod
    def a():
      n, *xy = map(int, sys.stdin.read().split())
      *xy, = zip(*[iter(xy)]*2)
      print(xy)
      pass



  class TDPC:
    @staticmethod
    def t():
      pass




  class MSolutions2020:
    @staticmethod
    def a():
      x = int(sys.stdin.readline().rstrip())
      x -= 400
      print(8-x//200)

    @staticmethod
    def b():
      r, g, b, k = map(int, sys.stdin.read().split())
      while k and g <= r:
        g *= 2
        k -= 1
      while k and b <= g:
        b *= 2
        k -= 1
      print('Yes' if r < g < b else 'No')

    @staticmethod
    def c():
      n, k, *a = map(int, sys.stdin.read().split())
      for i in range(k, n):
        print('Yes' if a[i] > a[i-k] else 'No')

    @staticmethod
    def d():
      n, *a = map(int, sys.stdin.read().split())
      a += [-1]
      m = 1000
      s = 0
      for i in range(n):
        if a[i+1] == a[i]: continue
        elif a[i+1] > a[i]:
          cnt = m//a[i]
          m -= a[i]*cnt
          s += cnt
        else:
          m += a[i]*s
          s = 0
      print(m)


class Codeforces:
  class CR676div2:
    @staticmethod
    def a():
      t = int(sys.stdin.readline().rstrip())
      for _ in range(t):
        a, b = map(int, sys.stdin.readline().split())
        print(a^b)

    @staticmethod
    def b():
      t = int(sys.stdin.readline().rstrip())
      for _ in range(t):
        n = int(sys.stdin.readline().rstrip())
        s = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
        s[0][0] = s[-1][-1] = '0'
        for i in range(n):
          for j in range(n):
            s[i][j] = int(s[i][j])


        def can_goal(g, c=0):
          visited = [0] * n
          stack = [(0, 0)]
          visited[0] |= 1<<0
          while stack:
            y, x = stack.pop()
            for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
              i, j = y+dy, x+dx
              if i<0 or i>=n or j<0 or j>=n: continue
              if i == j == n-1: return True
              if visited[i]>>j&1: continue
              visited[i] |= 1<<j
              if g[i][j] != c: continue
              stack.append((i, j))
          return False

        if not (can_goal(s, 0) or can_goal(s, 1)):
          print(0)
          continue

        flg = 0
        for i in range(n):
          for j in range(n):
            if i==j==0 or i==j==n-1: continue
            s[i][j] ^= 1
            if not (can_goal(s, 0) or can_goal(s, 1)):
              print(1)
              print(i+1, j+1)
              flg = 1
              break
            s[i][j] ^= 1
          if flg: break
        if flg: continue

        print(2)
        if s[0][1] == s[1][0]:
          print(n, n-1)
          print(n-1, n)
          continue

        if s[0][1] == s[-1][-2]:
          print(1, 2)
          print(n-1, n)
        else:
          print(1, 2)
          print(n, n-1)



    @staticmethod
    def c():
      pass

class ProjectEuler:
  @staticmethod
  def p1():
    def f(n, x):
      return (x + n//x*x) * (n//x) // 2
    n = 1000
    ans = f(n-1, 3)+f(n-1, 5)-f(n-1, 15)
    print(ans)

  @staticmethod
  def p2():
    fib = [1, 2]
    while fib[-1] < 4*10**6:
      fib.append(fib[-1]+fib[-2])
    print(sum(fib[1:-1:3]))

  @staticmethod
  def p3():
    pn = NumberTheory.PrimeNumbers()
    res = pn.factorize(600851475143)
    print(max(res.keys()))

  @staticmethod
  def p4():
    def is_palindrome(n):
      n = str(n)
      return n == n[::-1]
    cand = []
    for a in range(100, 1000):
      for b in range(a, 1000):
        n = a*b
        if is_palindrome(n): cand.append(n)
    print(max(cand))

  @staticmethod
  def p5():
    pn = NumberTheory.PrimeNumbers()
    res = defaultdict(int)
    for i in range(1, 21):
      for p, c in pn.factorize(i).items():
        res[p] = max(res[p], c)
    ans = 1
    for p, c in res.items(): ans *= pow(p, c)
    print(ans)

  @staticmethod
  def p6():
    a = np.arange(101)
    b = np.cumsum(a**2)
    a = a.cumsum()
    print(a[100]**2 - b[100])

  @staticmethod
  def p7():
    nt = NumberTheory.PrimeNumbers()
    print(sorted(nt)[10000])
  @staticmethod
  def p8():
    n = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
    n = [int(d) for d in list(n)]
    res = 0
    for i in range(988):
      x = 1
      for j in range(13):
        x *= n[i+j]
      res = max(res, x)
    print(res)
  @staticmethod
  def p9():
    for a in range(1, 997):
      for b in range(a, 998-a):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
          print(a*b*c)
          return
  @staticmethod
  def p10():
    pn = NumberTheory.PrimeNumbers(2*10**6+1)
    print(sum(pn))
  @staticmethod
  def p11():
    grid = '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'
    print(grid)

  pass

class Yukicoder:
  def __init__(self):
    pass

  def __call__(self):
    print(1)


class AOJ:
  @staticmethod
  def ALDS1_12_A():
    n, *a = map(int, sys.stdin.read().split())
    g = GeometryTopology.Graph(n)
    for i in range(n-1):
      for j in range(i+1, n):
        if a[i*n+j] == -1: continue
        g.add_edge(i,j, weight=a[i*n+j])
        g.add_edge(j,i, weight=a[i*n+j])
    _, d = g.kruskal()
    # _, d = g.prim()
    # _, d = g.boruvka()
    print(d)


  @staticmethod
  def GRL_3_C(): # strongly connected components
    n, m = map(int, sys.stdin.readline().split())
    g = GeometryTopology.Graph(n)
    for _ in range(m): g.add_edge(*map(int, sys.stdin.readline().split()))
    r = g.scc()
    q, *uv = map(int, sys.stdin.read().split())
    for u, v in zip(*[iter(uv)] * 2): print(int(r[u]==r[v]))


class YosupoJudge:
  @staticmethod
  def Directed_MST():
    n, m, s, *abc = map(int, sys.stdin.read().split())
    g = GeometryTopology.Graph(n)
    for a, b, c in zip(*[iter(abc)]*3):g.add_edge(a, b, weight=c)
    _, d, p = g.prim(src=s, return_parent=True)
    print(d)
    print(*p)

  @staticmethod
  def Manhattan_MST():
      n, *xy = map(int, sys.stdin.read().split())
      g = GeometryTopology.Graph(n)

if __name__ == '__main__':
  # AtCoder.ABC105.d()
  AtCoder.ARC107.c()
  pass
