题目描述

一个原子在坐标平面的原点，需要移到去。为了尽快到达目的地，它不希望向左或向下走，每一步只能是向右或向上。与此同时，平面上还有个能量补给点，原子的运动路径需要经过全部个特殊点获得足够的运动能量。 请为原子规划一条满足约束的最短路径。输入数据保证这样的路径存在且唯一。

输入格式

输入的第1行包含2个整数，表示目的地的横坐标和纵坐标。

接下来1行1个整数，表示补给点的总数。

接下来行，第行包含2个整数，描述第个补给点的横坐标和纵坐标。

输出格式

输出1行个整数，描述满足约束的最短路径。具体地，设输出序列为，原子路径将从开始，依次经过第个特殊点、第个特殊点……第个特殊点，最后抵达并结束。

样例

5 5
2
3 2
2 2

2 1

解释#1

下图是一条满足约束的最短路径。因为在这条路径上原子先经过点2再经过点1，所以程序应该输出2 1。

数据范围

• 对于全部数据，有$1<=n<=10^5$,$1<=r,c,xi,yi<=10^9$。
• 测试点1~ 3（共30分）：n<=10。
• 测试点4~ 7（共40分）：n<=4000。
• 测试点8~ 10（共30分）：无特殊限制。