斯洛伐克公司 WKD（Wiosła Kardynalnie Dobre，即“极其优质的桨”）生产出了 $n$ 种新型号的桨！ 该公司并没有一个良好的方法来衡量其产品的升力，因此他们雇佣了一位专业的桨测试员——斯沃米尔。 不幸的是，他评估桨升力的方法也并不十分准确——他会拿出每一对可能的桨，坐进小船中，划到浮标再划回来。 然后他会记录如下内容： 我可以肯定，这对桨的总升力不超过 $x$，但其中一只桨的升力一定至少为 $y$，因为我的手感到疲惫了。

测试结束后，斯沃米尔把结果交给了WKD的主管米罗斯瓦娃。 然而她认为，这些数据太多，而且意义不大。 她更希望知道的是：给出任意一组桨的升力值，使得这些值满足测试员提供的信息即可。 请输出这样一组升力值。

输入格式

输入的第一行是一个整数 $n$（$1 \le n \le 300$），表示桨的种类数量。桨的种类编号为 1 到 $n$。 接下来的 $n$ 行，每行有 $n$ 个数字：第 $i$ 行的第 $j$ 个数字为 $x_{ij}$（$1 \le x_{ij} \le 10^9$），表示种类 $i$ 和种类 $j$ 的桨的总升力上限。

接着是一个空行。

然后是 $n$ 行，每行也有 $n$ 个数字。第 $i$ 行的第 $j$ 个数字为 $y_{ij}$（$1 \le y_{ij} \le 10^9$）。这表示第 $i$ 种桨或第 $j$ 种桨的升力至少为 $y_{ij}$。

输出格式

输出 $n$ 个正整数，第 $i$ 个数字表示种类 $i$ 的桨在某一组与测试信息一致的升力取值中的升力值。 你可以假设一定存在一个满足要求的解。

示例

输入

3
6 8 5
7 6 6
5 7 7

2 3 1
3 1 1
2 1 3

输出

2 3 3