Chef and his friend Miron were getting bored and decided to play a game. 
Miron thinks of a sequence of  N  integers (A1, A2, …., AN) and gives Chef a matrix B, where Bi,j = |Ai - Aj|. He further tells Chef that A1 = 0. The game is for Chef to guess the sequence that Miron thought of. 
But Miron is an adversarial player. Every time Chef tries to guess the sequence, he makes a change to the matrix. He makes such a change Q times. Each time, he replaces an entry in some row and the corresponding column with a new one leaving Chef to guess the sequence after each change. 
Chef needs a friend to help him against such an adversarial player. Can you be that friend and help Chef find a suitable sequence A for the initial matrix B and also after each change Miron makes? 
Note that if several answers exist, then print the lexicographically smallest answer. Further, the numbers in the sequence can be negative.

-----Input-----

The first line contains two space-separated integers N, Q. Each of the N subsequent lines contains N space-separated integers, denoting the matrix B.

Q queries follow. Each query has two lines. The first line of each query contains an integer p, denoting the number of row and column that is changed. The second line of each query contains N space-separated integers F1, F2, F3, ... FN, denoting the new values to the corresponding cells of the matrix (you should make the following assignments Bi,p = Bp,i = Fi for all valid i). 

-----Output-----
Print Q + 1 lines which contain N space-separated integers, Miron's initial array and Miron's array after each query.

-----Constraints-----
- 3 ≤ N ≤  1000 
- 1 ≤ Q ≤  1000 
- 0 ≤ Bi,j ≤  5000 
- 1 ≤ p ≤  n 
- 0 ≤ Fi ≤  5000 
- it's guaranteed there's always an answer

-----Example-----
Input:
3 2
0 1 2
1 0 1
2 1 0
1
0 4 3
2
4 0 7
Output:
0 -1 -2
0 -4 -3
0 -4 3

-----Explanation-----
Example case 1. Initially, sequence {0, 1, 2} is also suitable, but {0, -1, -2} is lexicografically smaller.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def update_B(B, query):\n p, R = query\n for i in range(len(R)):\n  B[p][i] = R[i]\n  B[i][p] = R[i]\n\ndef get_A(B):\n N = len(B)\n A = [0] * N\n i = 0\n for j in range(N):\n  if B[0][j] != 0:\n   i = j\n   A[i] = -B[0][i]\n   break\n\n for j in range(i + 1, N):\n  if abs(A[i] - B[0][j]) == B[i][j]:\n   A[j] = B[0][j]\n  else:\n   A[j] = -B[0][j]\n\n return A\n\ndef print_list(A):\n print(' '.join([str(a) for a in get_A(B)]))\n\n\nN, Q = [int(x) for x in input().rstrip().split()]\nB = []\nfor i in range(N):\n B += [[int(x) for x in input().rstrip().split()]]\nqueries = []\nfor i in range(Q):\n p = int(input()) - 1\n arr = input().rstrip().split()\n queries += [(p, [int(x) for x in arr])]\n\nprint_list(get_A(B))\nfor q in queries:\n update_B(B, q)\n print_list(' '.join([str(a) for a in get_A(B)]))\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14019