code: from __future__ import annotations
  
  from typing import Generator, NoReturn
  
  
  class StdReader:
      def __init__(
          self,
      ) -> NoReturn:
          import sys
  
          self.buf = sys.stdin.buffer
          self.lines = self.async_readlines()
          self.chunks: Generator
  
      def async_readlines(
          self,
      ) -> Generator:
          while True:
              gen = self.line_chunks()
              yield gen
  
      def line_chunks(
          self,
      ) -> Generator:
          ln = self.buf.readline()
          for chunk in ln.split():
              yield chunk
  
      def __call__(
          self,
      ) -> bytes:
          try:
              chunk = next(self.chunks)
          except:
              self.chunks = next(
                  self.lines,
              )
              chunk = self()
          return chunk
  
      def str(
          self,
      ) -> str:
          b = self()
          return b.decode()
  
      def int(
          self,
      ) -> int:
          return int(self.str())
  
  
  from abc import ABC, abstractmethod
  
  
  class Solver(ABC):
      def __init__(self):
          self.reader = StdReader()
  
      def __call__(
          self,
      ):
          self.prepare()
          self.solve()
  
      @abstractmethod
      def prepare(self):
          ...
  
      @abstractmethod
      def solve(self):
          ...
  
  
  import numpy as np
  from scipy.sparse import csr_matrix
  from scipy.sparse.csgraph import floyd_warshall
  
  
  class Problem(
      Solver,
  ):
      def prepare(self):
          reader = self.reader
          n = reader.int()
          m = reader.int()
          a = [reader.int() for _ in range(3 * m)]
          a = np.array(
              a,
          ).reshape(m, 3)
          a, b, t = a.T
          self.n, self.m = n, m
          self.a = a - 1
          self.b = b - 1
          self.t = t
  
      def solve(self):
          self.compute_dist_mat()
          dist = self.dist
          d = dist.max(axis=1).min()
          print(int(d))
  
      def compute_dist_mat(
          self,
      ):
          n = self.n
          a = self.a
          b = self.b
          t = self.t
          g = csr_matrix(
              (t, (a, b)),
              shape=(n, n),
          )
          dist = floyd_warshall(
              csgraph=g,
              directed=False,
          )
          self.dist = dist
  
  
  def main():
      t = 1
      # t = StdReader().int()
      for _ in range(t):
          Problem()()
  
  
  if __name__ == "__main__":
      main()
   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**0.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**0.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**0.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 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**0.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) - 0.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():
              pass
  
      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():
              pass
  
          @staticmethod
          def b():
              pass
  
          @staticmethod
          def c():
              pass
  
          @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():
              pass
  
          @staticmethod
          def b():
              pass
  
          @staticmethod
          def c():
              pass
  
          @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():
              pass
  
          @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))
              # a +=
              print(2 * n)
              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:
          pass
  
      class ABC083:
          pass
  
      class ABC084:
          pass
  
      class ABC085:
          pass
  
      class ABC086:
          pass
  
      class ABC087:
          pass
  
      class ABC088:
          pass
  
      class ABC089:
          pass
  
      class ABC090:
          pass
  
      class ABC091:
          pass
  
      class ABC092:
          pass
  
      class ABC093:
          pass
  
      class ABC094:
          pass
  
      class ABC095:
          pass
  
      class ABC096:
          pass
  
      class ABC097:
          pass
  
      class ABC098:
          pass
  
      class ABC099:
          pass
  
      class ABC100:
          pass
  
      class ABC101:
          pass
  
      class ABC102:
          pass
  
      class ABC103:
          pass
  
      class ABC104:
          pass
  
      class ABC105:
          pass
  
      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 = n - pow(3, a)
                  b = 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)
  
              visited = [False] * n
              ga = [[] for _ in range(n)]
              gb = [[] 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 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.ABC179.f()
      # AtCoder.ABC060.d()
      AtCoder.ABC081.d()
      # AtCoder.ARC106.d()
      # YosupoJudge.Directed_MST()
      pass
  
apis: numpy.array scipy.sparse.csr_matrix scipy.sparse.csgraph.floyd_warshall
apis: numpy.logical_or numpy.ones numpy.sum numpy.any numpy.argsort numpy.logical_or.at numpy.fill_diagonal numpy.amax numpy.append scipy.optimize numpy.absolute numpy.subtract.at numpy.identity numpy.unique numpy.flatnonzero numpy.minimum numpy.sqrt numpy.eye numpy.minimum.at numpy.nonzero numpy.bincount scipy.ndimage.distance_transform_cdt numpy.zeros scipy.optimize.bisect numpy.equal numpy.add.at numpy.count_nonzero numpy.arange scipy.sparse.csgraph.connected_components numpy.hstack numpy.maximum numpy.sort numpy.pad numpy.resize numpy.zeros_like numpy.cumsum numpy.bitwise_xor.reduce scipy.sparse.csr_matrix scipy.optimize.brenth scipy.sparse.csgraph.shortest_path numpy.ravel numpy.amin numpy.array numpy.sin numpy.dot numpy.full