Копатыч тайно готовится к вторжению марсиан.
Участок Копатыча представляет собой клетчатое поле из $$$n$$$ строк и $$$m$$$ столбцов. Копатыч заранее установил $$$2 k$$$ систем вентиляции в различных позициях $$$(x_1, y_1), (x_2, y_2), \ldots, (x_{2k}, y_{2k})$$$.
Для длительной обороны необходимо выкопать $$$k$$$ подкопов. Каждый подкоп должен соединять какую-то пару систем вентиляции. Каждая система вентиляции должна быть частью ровно одного подкопа. Чтобы система подкопов была отказоустойчивой, никакие два подкопа не должны пересекаться. Другими словами, каждая клетка участка может принадлежать не более чем одному подкопу.
Помогите Копатычу подготовить подкопы для обороны.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны целые числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n, m \le 500$$$, $$$2 \le \max(n, m)$$$, $$$1 \le k \le \frac{n \cdot m}{2}$$$) — количество строк, столбцов и подкопов.
В следующих $$$2 k$$$ строках каждого набора даны пары чисел $$$(x_1, y_1), (x_2, y_2), \ldots, (x_{2k}, y_{2k})$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — позиции систем вентиляции.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.
Для каждого набора входных данных выведите описания $$$k$$$ подкопов.
Описание каждого подкопа должно содержать в первой строке число $$$s_i$$$ — количество клеток участка в $$$i$$$-м подкопе.
Следующие $$$s_i$$$ строк должны содержать по два целых числа $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — описание клеток подкопа. Первая и последняя клетки должны содержать системы вентиляции. Соседние клетки должны быть соседними по стороне.
3 3 3 2 1 1 1 3 3 1 3 3 3 5 3 3 3 1 1 1 3 1 4 2 5 2 1 4 4 1 4 1 1 4
3 1 1 1 2 1 3 3 3 1 3 2 3 3 2 1 1 2 1 2 1 3 1 4 4 3 3 3 4 3 5 2 5 7 4 1 3 1 2 1 1 1 1 2 1 3 1 4
В первом наборе входных данных мы можем соединить подкопом первую систему вентиляции со второй, подкопом с координатами $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, а третью систему вентиляции с четвертой подкопом с координатами $$$(3, 1)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$ (см. картинку).
