题目描述

小爱开着新买的车刚刚驶入停车场，这个露天停车场可以看作一个以$(0,0)$作为左下角，大小为$500 \times 500$的方格矩阵，小爱当前在入口$(0,0)$处，当前时间计为$t=0$，车辆每秒可移动至上下左右四个相邻的方格内。 突然一阵冰雹雨来袭，鸡蛋大小的冰雹从天而降，令人很是恐惧。小爱第一时间就预推测了冰雹的未来趋势，他推测出这一场冰雹雨一共会有$n$颗冰雹落下，其中第$i$颗冰雹会在$t_i$时刻落在$(x_i,y_i)$位置，且由于冰雹威力太大，落下的冰雹会在$t_i+1$时刻波及$(x_i,y_i)$周围上下左右的四个格子。如果一个格子被冰雹砸中，那么这个格子在被冰雹波及之后，小爱的车也不能经过。 小爱当然不希望自己刚买的爱车被冰雹砸中，他想知道是否存在一种方案让他到达一个安全的位置，如果存在，输出到达安全位置的最短时间，反之输出No Solution

输入格式

第一行，一个正整数$n$，表示冰雹数量 接下来$n$行，每行三个非负整数$t_i,x_i,y_i$，表示$t_i$时刻有一冰雹落至$(x_i,y_i)$处。

输出格式

输出最短到达安全位置的时间，若无法到达以安全位置，输出No Solution

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

3

样例解释 1

第一秒从(0,0)至(0,1)； 第二秒从(0,1)至(0,2)； 第三秒从(0,2)至(1,2)，到达安全位置。

数据范围

• 对于 $50\%$ 的数据， $1 \leq n \leq 100$；
• 对于 $100\%$ 的数据， $1 \leq n \leq 10^4$ $0\leq x_i,y_i\lt 400$，$t_i\leq 10^3$。