maehrm

import sys

input = lambda: sys.stdin.readline().rstrip()


def main():
    N, Q = map(int, input().split())
    H = [N] * (N + 1)           # H[c]:列cにおける白の位置(最初はN行目)
    W = [N] * (N + 1)           # W[r]:行rにおける白の位置(最初はN列目)
    min_row, min_col = N, N     # これまでに配置された行,列の最小値

maehrm

import sys

sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().strip()


def main():
    N, A, B, C = map(int, input().split())
    S = [input() for _ in range(N)]
    ans = []

maehrm

import sys

from atcoder.segtree import SegTree

input = lambda: sys.stdin.readline()


def main():
    N, C = map(int, input().split())
    M = int(input())

maehrm

import sys
from collections import defaultdict

input = lambda: sys.stdin.readline()


def main():
    N, M = map(int, input().split())
    blacks = defaultdict(list)
    for _ in range(M):

maehrm

import sys

input = lambda: sys.stdin.readline()


def get_divisor(n):
    ret = []
    i = 1
    while i * i <= n:
        if n % i == 0:

maehrm

import sys
from bisect import bisect_left

input = lambda: sys.stdin.readline()


def main():
    N = int(input())
    lis = []  # LISを使って解く。lisに入る数値は動かさなくてもよい
    for _ in range(N):

maehrm

import sys

input = lambda: sys.stdin.readline()


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

maehrm

import sys
from collections import deque

input = lambda: sys.stdin.readline()


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):

maehrm

import sys

input = lambda: sys.stdin.readline()


def main():
    N = int(input())
    low, high = -float("inf"), float("inf")
    add = 0
    for _ in range(N):

maehrm

import sys

input = lambda: sys.stdin.readline()


def main():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    def check(v):