Description
天依发现天钿陷入了一个N*M的迷宫内，在这个迷宫里有一些地方有障碍物，还有一些地方有小笼包OvO，现在，天依位于迷宫的(1,1) 位置，天钿位于(x,y)的位置，在迷宫中有一些位置有k个障碍，天依不能通过，还有P个地方有天依最喜欢的小笼包。
天依希望用最少的步数找到天钿，同时获得尽可能多的小笼包，天依只能往4个方向走。由于天依实在是太着急了，所以她只能等待1s，如果无法找到天钿，请输出QAQ
Input
第一行6个整数，N,M,x,y,K,P
接下来K行，每行2个整数p,q，表示(p,q)位置存在障碍
接下来P行，每行3个整数u,v,w ，表示(u,v)位置有w个小笼包
Output
若干行，第一行2个整数，分别表示最小步数和最小步数下能获得的最多的小笼包
下面输出若干行，表示天依行走的路径，用数对表示，如果有多组答案，请输出字典序最小的
Tips:本题中字典序的定义为：设(x1,y1)与(x2,y2)，若满足(x1==x2 且 y1<y2) 或 x1 < x2，则我们称(x1,y1)<(x2,y2)，
3 3 3 3 1 5
2 2
1 1 1
1 2 1
1 3 1
2 1 1
2 3 5
4 8
(1,1)
(1,2)
(1,3)
(2,3)
(3,3)
HINT
对于 60% 的数据，N,M <= 100$
对于 100% 的数据，N,M <= 1000;K,P <= min(N*M,2000);w <= 109，保证所给的点均在地图范围内