Space Harbour (Codeforces 1925E)
Tags: Math, data structures

There are $$$n$$$ points numbered $$$1$$$ to $$$n$$$ on a straight line. Initially, there are $$$m$$$ harbours. The $$$i$$$-th harbour is at point $$$X_i$$$ and has a value $$$V_i$$$. It is guaranteed that there are harbours at the points $$$1$$$ and $$$n$$$. There is exactly one ship on each of the $$$n$$$ points. The cost of moving a ship from its current location to the next harbour is the product of the value of the nearest harbour to its left and the distance from the nearest harbour to its right. Specifically, if a ship is already at a harbour, the cost of moving it to the next harbour is $$$0$$$. Additionally, there are $$$q$$$ queries, each of which is either of the following $$$2$$$ types:  $$$1$$$ $$$x$$$ $$$v$$$ — Add a harbour at point $$$x$$$ with value $$$v$$$. It is guaranteed that before adding the harbour, there is no harbour at point $$$x$$$.  $$$2$$$ $$$l$$$ $$$r$$$ — Print the sum of the cost of moving all ships at points from $$$l$$$ to $$$r$$$ to their next harbours. Note that you just need to calculate the cost of moving the ships but not actually move them. 

Input: The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le m \le n \le 3 \cdot 10^5$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — the number of points, harbours, and queries, respectively.The second line contains $$$m$$$ distinct integers $$$X_1, X_2, \ldots, X_m(1 \le X_i \le n)$$$ — the position at which the $$$i$$$-th harbour is located.The third line contains $$$m$$$ integers $$$V_1, V_2, \ldots, V_m(1 \le V_i \le 10^7)$$$ — the value of the $$$i$$$-th harbour.Each of the next $$$q$$$ lines contains three integers. The first integer is $$$t$$$ ($$$1\le t \le 2$$$) — type of query. If $$$t=1$$$, then the next two integers are $$$x$$$ and $$$v$$$ ($$$2 \le x \le n - 1$$$, $$$1 \le v \le 10^7$$$) — first-type query. If $$$t=2$$$, then the next two integers are $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — second-type query.It is guaranteed that there is at least one second-type query.

Output: For every second-type query, print one integer in a new line — answer to this query.

Note: For the first type $$$2$$$ query, the cost for ships at positions $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ are $$$3(3 \times 1)$$$, $$$0$$$, $$$96(24 \times 4)$$$ and $$$72(24 \times 3)$$$ respectively.For the second type $$$2$$$ query, since the ship at position $$$5$$$ is already at a harbour, so the cost is $$$0$$$.For the third type $$$2$$$ query, the cost for ships at position $$$7$$$ and $$$8$$$ are $$$15(15 \times 1)$$$ and $$$0$$$ respectively.

Sample Inputs:
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8

Sample Outputs:
171
0
15

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

class FenwickTree:

    def __init__(self, n):
        self.n = n
        self.bit = [0] * n

    def update(self, idx, delta):
        """"""
        while idx < self.n:
            self.bit[idx] += delta
            idx |= idx + 1

    def query(self, idx):
        """"""
        res = 0
        while idx >= 0:
            res += self.bit[idx]
            idx = (idx & idx + 1) - 1
        return res

    def sum(self, left_index, right_idx):
        """"""
        return self.query(right_idx - 1) - self.query(left_index - 1)

    def find_kth(self, k):
        """"""
        idx = -1
        for d in range(self.n.bit_length() - 1, -1, -1):
            right_idx = idx + (1 << d)
            if right_idx < self.n and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1
(n, m, q) = map(int, input().split())
X = list(map(lambda x: int(x) - 1, input().split()))
V = list(map(int, input().split()))
harbour_values = [0] * n
for (x, v) in zip(X, V):
    harbour_values[x] = v
fenwick_harbours = FenwickTree(n)
for x in X:
    fenwick_harbours.update(x, 1)

def get_harbour_to_left(x):
    if harbour_values[x]:
        return x
    sm = fenwick_harbours.query(x)
    return fenwick_harbours.find_kth(sm - 1)

def get_harbour_to_right(x):
    if harbour_values[x]:
        return x
    sm = fenwick_harbours.query(x)
    return fenwick_harbours.find_kth(sm)
fenwick_costs = FenwickTree(n)
fenwick_cost_vals = [0] * n
idx = sorted(range(m), key=lambda i: X[i])
for i in range(1, m):
    left_harbour = X[idx[i - 1]]
    left_harbour_value = harbour_values[left_harbour]
    habour = X[idx[i]]
    fenwick_cost_vals[habour] = (habour - left_harbour - 1) * (habour - left_harbour) // 2 * left_harbour_value
    fenwick_costs.update(habour, fenwick_cost_vals[habour])
ans = []
for _ in range(q):
    (t, *inp) = map(int, input().split())
    if t == 1:
        (new_harbour, new_harbour_value) = inp
        new_harbour -= 1
        left_harbour = get_harbour_to_left(new_harbour)
        left_harbour_value = harbour_values[left_harbour]
        right_harbour = get_harbour_to_right(new_harbour)
        fenwick_harbours.update(new_harbour, 1)
        harbour_values[new_harbour] = new_harbour_value
        d = new_harbour - left_harbour - 1
        fenwick_cost_vals[new_harbour] = d * (d + 1) // 2 * left_harbour_value
        fenwick_costs.update(new_harbour, fenwick_cost_vals[new_harbour])
        d = right_harbour - new_harbour - 1
        delta = d * (d + 1) // 2 * new_harbour_value - fenwick_cost_vals[right_harbour]
        fenwick_cost_vals[right_harbour] += delta
        fenwick_costs.update(right_harbour, delta)
    elif t == 2:
        (l, r) = inp
        l -= 1
        r -= 1
        if get_harbour_to_right(l) > r:
            left_harbour = get_harbour_to_left(l)
            right_harbour = get_harbour_to_right(r)
            left_harbour_value = harbour_values[left_harbour]
            d1 = right_harbour - l
            d2 = right_harbour - (r + 1)
            res = (d1 * (d1 + 1) // 2 - d2 * (d2 + 1) // 2) * left_harbour_value
            ans += [str(res)]
            continue
        res = fenwick_costs.sum(l, r + 1)
        left_harbour = get_harbour_to_left(l)
        if left_harbour == l:
            res -= fenwick_cost_vals[l]
        else:
            left_harbour_value = harbour_values[left_harbour]
            harbour = get_harbour_to_right(left_harbour + 1)
            d1 = harbour - (left_harbour + 1)
            d2 = harbour - l
            res -= (d1 * (d1 + 1) // 2 - d2 * (d2 + 1) // 2) * left_harbour_value
        right_harbour = get_harbour_to_right(r)
        if r < right_harbour:
            res += fenwick_cost_vals[right_harbour]
        harbour = get_harbour_to_left(right_harbour - 1)
        harbour_value = harbour_values[harbour]
        d = right_harbour - (r + 1)
        res -= d * (d + 1) // 2 * harbour_value
        ans += [str(res)]
print('\n'.join(ans))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()

class FenwickTree:

    def __init__(self, n):
        self.n = n
        self.bit = [0] * n

    def update(self, idx, delta):
        """"""
        while idx < self.n:
            self.bit[idx] += delta
            idx |= idx + 1

    def query(self, idx):
        """"""
        res = 0
        while idx >= 0:
            res += self.bit[idx]
            idx = (idx & idx + 1) - 1
        return res

    def sum(self, left_index, right_idx):
        """"""
        return self.query(right_idx - 1) - self.query(left_index - 1)

    def find_kth(self, k):
        """"""
        idx = -1
        for d in range(self.n.bit_length() - 1, -1, -1):
            right_idx = idx + (1 << d)
            if right_idx < self.n and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1
(n, m, q) = map(int, input().split())
X = list(map(lambda x: int(x) - 1, input().split()))
V = list(map(int, input().split()))
harbour_values = [0] * n
for (x, v) in zip(X, V):
    harbour_values[x] = v
fenwick_harbours = FenwickTree(n)
for x in X:
    fenwick_harbours.update(x, 1)

def get_harbour_to_left(x):
    if harbour_values[x]:
        return x
    sm = fenwick_harbours.query(x)
    return fenwick_harbours.find_kth(sm - 1)

def get_harbour_to_right(x):
    if harbour_values[x]:
        return x
    sm = fenwick_harbours.query(x)
    return fenwick_harbours.find_kth(sm)
fenwick_costs = FenwickTree(n)
fenwick_cost_vals = [0] * n
idx = sorted(range(m), key=lambda i: X[i])
for i in range(1, m):
    left_harbour = X[idx[i - 1]]
    left_harbour_value = harbour_values[left_harbour]
    habour = X[idx[i]]
    fenwick_cost_vals[habour] = (habour - left_harbour - 1) * (habour - left_harbour) // 2 * left_harbour_value
    fenwick_costs.update(habour, fenwick_cost_vals[habour])
for _ in range(q):
    (t, *inp) = map(int, input().split())
    if t == 1:
        (new_harbour, new_harbour_value) = inp
        new_harbour -= 1
        left_harbour = get_harbour_to_left(new_harbour)
        left_harbour_value = harbour_values[left_harbour]
        right_harbour = get_harbour_to_right(new_harbour)
        fenwick_harbours.update(new_harbour, 1)
        harbour_values[new_harbour] = new_harbour_value
        d = new_harbour - left_harbour - 1
        fenwick_cost_vals[new_harbour] = d * (d + 1) // 2 * left_harbour_value
        fenwick_costs.update(new_harbour, fenwick_cost_vals[new_harbour])
        d = right_harbour - new_harbour - 1
        delta = d * (d + 1) // 2 * new_harbour_value - fenwick_cost_vals[right_harbour]
        fenwick_cost_vals[right_harbour] += delta
        fenwick_costs.update(right_harbour, delta)
    elif t == 2:
        (l, r) = inp
        l -= 1
        r -= 1
        if get_harbour_to_right(l) > r:
            left_harbour = get_harbour_to_left(l)
            right_harbour = get_harbour_to_right(r)
            left_harbour_value = harbour_values[left_harbour]
            d1 = right_harbour - l
            d2 = right_harbour - (r + 1)
            ans = (d1 * (d1 + 1) // 2 - d2 * (d2 + 1) // 2) * left_harbour_value
            print(ans)
            continue
        ans = fenwick_costs.sum(l, r + 1)
        left_harbour = get_harbour_to_left(l)
        if left_harbour == l:
            ans -= fenwick_cost_vals[l]
        else:
            left_harbour_value = harbour_values[left_harbour]
            harbour = get_harbour_to_right(left_harbour + 1)
            d1 = harbour - (left_harbour + 1)
            d2 = harbour - l
            ans -= (d1 * (d1 + 1) // 2 - d2 * (d2 + 1) // 2) * left_harbour_value
        right_harbour = get_harbour_to_right(r)
        if r < right_harbour:
            ans += fenwick_cost_vals[right_harbour]
        harbour = get_harbour_to_left(right_harbour - 1)
        harbour_value = harbour_values[harbour]
        d = right_harbour - (r + 1)
        ans -= d * (d + 1) // 2 * harbour_value
        print(ans)

Solution (Python):
class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

    def __init__(self, arg):
        super().__init__(arg)

    def rangeCountByValue(self, leftVal, rightVal):
        leftCummulative = self.bisect_left(leftVal)
        rightCummulative = self.bisect_left(rightVal + 1)
        return rightCummulative - leftCummulative

class FenwickTree:

    def __init__(self, x):
        """"""
        self.bit = x
        for i in range(len(x)):
            j = i | i + 1
            if j < len(x):
                x[j] += x[i]

    def update(self, idx, x):
        """"""
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1

    def query(self, end):
        """"""
        end += 1
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x

    def findkth(self, k):
        """"""
        idx = -1
        for d in reversed(range(len(self.bit).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(self.bit) and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1

def make_range_query(seg_arr):
    sa = seg_arr.copy()
    FT = FenwickTree(sa.copy())

    def update(pos, val):
        change = val - sa[pos]
        sa[pos] = val
        FT.update(pos, change)
        return

    def query(l, r):
        if l - 1 >= 0:
            return FT.query(r) - FT.query(l - 1)
        else:
            return FT.query(r)
    return (update, query)

def solve(n, m, q, initial_xes, initial_ves, queries):

    def calc_cost_full_gap(v_left, z):
        return (1 + z) * z // 2 * v_left

    def find_next_left_and_right(x):
        if x == 1 or x == n:
            return (x, x)
        i = x_pos_sl.bisect_left(x)
        next_left_x = x_pos_sl[i - 1]
        next_right_x = x_pos_sl[i]
        if x == next_right_x:
            return (x, x)
        return (next_left_x, next_right_x)
    v_map = [-1] * (n + 1)
    for i in range(m):
        v_map[initial_xes[i]] = initial_ves[i]
    x_pos_sl = SortedList(initial_xes)
    x_order = list(range(m))
    x_order.sort(key=lambda i: initial_xes[i])
    seg_arr = [0] * (n + 1)
    prev_v = v_map[1]
    l = 1
    for i in range(1, m):
        r = initial_xes[x_order[i]]
        z = r - l - 1
        seg_arr[r] = calc_cost_full_gap(prev_v, z)
        l = r
        prev_v = initial_ves[x_order[i]]
    (update, query) = make_range_query(seg_arr)
    allans = []
    for (t, X, Y) in queries:
        if t == 1:
            (x, v) = (X, Y)
            i = x_pos_sl.bisect_left(x)
            (next_left_x, next_right_x) = find_next_left_and_right(x)
            new_1 = calc_cost_full_gap(v_map[next_left_x], x - next_left_x - 1)
            update(x, new_1)
            new_2 = calc_cost_full_gap(v, next_right_x - x - 1)
            update(next_right_x, new_2)
            v_map[x] = v
            x_pos_sl.add(x)
        else:
            (l, r) = (X, Y)
            if l == n or r == 1:
                allans.append(0)
                continue
            (l_next_left_x, l_next_right_x) = find_next_left_and_right(l)
            (r_next_left_x, r_next_right_x) = find_next_left_and_right(r)
            if l_next_right_x == r_next_right_x:
                start = r_next_right_x - r
                end = r_next_right_x - l
                if l == l_next_left_x:
                    end -= 1
                num_terms = end - start + 1
                v_left = v_map[l_next_left_x]
                cost = (start + end) * num_terms // 2 * v_left
                ans = cost
            else:
                assert l_next_right_x <= r_next_left_x
                ans = 0
                if l_next_right_x < r_next_left_x:
                    ans = query(l_next_right_x + 1, r_next_left_x)
                if l < l_next_right_x:
                    v_left = v_map[l_next_left_x]
                    z = l_next_right_x - l
                    if l == l_next_left_x:
                        z -= 1
                    cost = z * (z + 1) // 2 * v_left
                    ans += cost
                if r_next_left_x < r:
                    start = r_next_right_x - r
                    end = r_next_right_x - r_next_left_x
                    end -= 1
                    num_terms = end - start + 1
                    v_left = v_map[r_next_left_x]
                    cost = (start + end) * num_terms // 2 * v_left
                    ans += cost
            allans.append(ans)
    return allans

def test():
    from random import randint
    (n, m, q) = (10, 3, 3)
    for _ in range(100):
        vi = {1, n}
        initial_xes = [1, n]
        initial_ves = [5, 5]
        while len(initial_xes) < m:
            x = randint(1, n)
            if x not in vi:
                vi.add(x)
                v = randint(1, n)
                initial_xes.append(x)
                initial_ves.append(v)
        queries = []
        for __ in range(q):
            op = randint(1, 2)
            (X, Y) = [randint(1, n) for __ in range(2)]
            if op == 2 and X > Y:
                (X, Y) = (Y, X)
            if op == 1:
                while X in vi:
                    X = randint(1, n)
                vi.add(X)
            queries.append((op, X, Y))
        print('new case')
        print(f'{n} {m} {q}')
        oneLineArrayPrint(initial_xes)
        oneLineArrayPrint(initial_ves)
        for qu in queries:
            oneLineArrayPrint(qu)
        print()
        allans = solve(n, m, q, initial_xes, initial_ves, queries)
        all_bf_ans = []
        ves = [-1] * (n + 1)
        for i in range(m):
            ves[initial_xes[i]] = initial_ves[i]
        for (op, X, Y) in queries:
            if op == 1:
                ves[X] = Y
            else:
                left_v = [0] * (n + 1)
                for x in range(1, n + 1):
                    if ves[x] != -1:
                        left_v[x] = ves[x]
                    else:
                        left_v[x] = left_v[x - 1]
                right_x = [-1] * (n + 1)
                for x in range(n, 0, -1):
                    if ves[x] != -1:
                        right_x[x] = 0
                    else:
                        right_x[x] = 1 + right_x[x + 1]
                ans = 0
                for x in range(X, Y + 1):
                    if ves[x] == -1:
                        ans += left_v[x] * right_x[x]
                all_bf_ans.append(ans)
        if allans != all_bf_ans:
            print(f'Wrong Answer!')
            print(f'n={n}\nm={m}\nq={q}\ninitial_xes={initial_xes}\ninitial_ves={initial_ves}\nqueries={queries}\nans={allans}bfans={all_bf_ans}')
            raise Exception()
    return

def main():
    (n, m, q) = readIntArr()
    initial_xes = readIntArr()
    initial_ves = readIntArr()
    queries = []
    for _ in range(q):
        (t, X, Y) = readIntArr()
        queries.append((t, X, Y))
    allans = solve(n, m, q, initial_xes, initial_ves, queries)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()