时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给一个 $n\times n$ 的网格图，从上到下第 $i$ 行，从左到右第 $j$ 列有一个高度为 $h_{i,j}$ 的柱子。

定义 $l_i$ 为：从第 $i$ 行的左侧看去，能看到多少根柱子；

• 如果一个更远的柱子的高度不超过一个更近的柱子的高度，那么其不会被看到。

定义 $r_i$ 为：从第 $i$ 行的右侧看去，能看到多少根柱子；

定义 $u_i$ 为：从第 $i$ 列的上侧看去，能看到多少根柱子；

定义 $d_i$ 为：从第 $i$ 列的下侧看去，能看到多少根柱子；

请对每个 $i\in [1,n]$，求出 $l_i,r_i,u_i,d_i$。

输入格式

从标准输入读入数据。

第一行，一个正整数 $n$；

接下来 $n$ 行，每行 $n$ 个正整数，其中第 $i$ 行第 $j$ 列为 $h_{i,j}$。

输出格式

输出到标准输出。

$n$ 行，每行四个正整数 $l_i,r_i,u_i,d_i$，意义如上所述。

4
3 4 2 1
2 1 4 3
4 3 1 2
1 2 3 4

2 3 2 2
2 2 1 3
1 3 2 2
4 1 3 1

样例 1 解释

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

3 1 3 2
5 2 4 2
2 3 2 3
3 3 3 3
1 4 3 2
3 2 2 4
6 2 2 3
2 4 5 1
5 2 3 3
2 3 1 4

数据范围

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

对于 $10\%$ 的数据，$n=1$；

对于 $20\%$ 的数据，$n\le 2$；

对于 $30\%$ 的数据，$n\le 3$；

对于 $40\%$ 的数据，$n\le 4$；

对于 $50\%$ 的数据，$n\le 5$；

对于 $60\%$ 的数据，$n\le 6$；

对于 $80\%$ 的数据，$n\le 20$；

对于 $100\%$ 的数据，$1\le n\le 100,~1\le h_{i,j}\le n$。