暂无测试数据。

题目描述

蒜头君收到了花椰妹的礼物，是一个 $n \times n$ 的棋盘。由于快递过于暴力，棋盘只剩下了一半。即棋盘的第一行只有一个格子，第二行有两个格子 $\cdots$ 第 $n$ 行有 $n$ 个格子。

蒜头君用数对 $(i, j)$ 表示位于棋盘第 $i$ 行第 $j$ 列的格子，并设计了如下的一个游戏：

游戏一共有 $q$ 轮， 第 $i$ 轮蒜头君会带着一个小球（小球上标有数 $x_i$ ）出发， 从棋盘 $(1,1)$ 处格子出发。

对于前 $n-1$ 行的所有格子 $(i, j)$ ，这些格子上有一个标有数 $Num_{i,j}$ 的小球 ，当蒜头君在格子 $(i,j)$ 的时候， 他会将自己手上的小球的数字 $x_i$ 与格子上的小球的数 $Num_{i,j}$ 进行比较， 如果 $x_i \le Num_{i,j}$ ， 那么他会走到格点 $(i+1,j)$ ， 否则他会走到格点 $(i+1,j+1)$ 。 当蒜头君走到第 $n$ 行的时候就会结束自己的旅程。

走完 $q$ 轮以后，游戏结束。蒜头君想问问聪明的你，对于每个格子，请问他共经过多少次。

输入格式

输入共 $n+1$ 行。

第一行两个正整数 $n,q$ ，分别代表棋盘的大小和游戏的轮数。

接下来 $n-1$ 行，第 $i (1\leq i< n)$ 行共 $i$ 个数，代表棋盘第 $i$ 行上 $i$ 个小球上标的数。

最后一行 $q$ 个正整数，第 $i$ 个正整数代表蒜头君第 $i$ 轮带的小球上标的数 $x_i$。

输出格式

输出 $n$ 行， 第 $i$ 行输出 $i$ 个整数，表示第 $i$ 行的$i$ 个格子蒜头君共经过了多少次。

数据范围

对于 $100 \%$ 的数据，满足 $1 \leq n \leq 1000,1 \leq q \leq 10^{5}, 1 \leq x_{i}, Num_{i, j} \leq 2 \times 10^{6}$。

本题共 $10$ 个测试点，各测试点详细信息见下表。

测试点编号	$n\le$	$q\le$	$Num_{i,j}\le$
$1$	$10$	$10$	$ 10$
$2$	$15$	$50$	$ 100$
$3$	$50$	$50$	$ 100$
$4$	$50$	$50$	$ 2×10^6$
$5$	$50$	$50$	$ 2×10^6$
$6$	$10^3$	$10^5$	$ 2×10^6$
$7$	$10^3$	$10^5$	$ 2×10^6$
$8$	$10^3$	$10^5$	$ 2×10^6$
$9$	$10^3$	$10^5$	$ 2×10^6$
$10$	$10^3$	$10^5$	$ 2×10^6$

5 5 
8
3 8
9 2 4 
6 5 8 2 
6 8 10 3 3

5
4 1 
2 2 1 
2 0 2 1 
2 0 2 0 1