2. Разбиение таблицы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим таблицу из $$$n$$$ строк и $$$m$$$ столбцов, в клетки которой по строкам записаны числа от $$$1$$$ до $$$n \cdot m$$$. Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами в клетку $$$(r, c)$$$ записано число $$$(r - 1) \cdot m + c$$$.

На рисунке приведен пример такой таблицы для $$$n = 3$$$, $$$m = 5$$$.

12345
678910
1112131415

Требуется разделить таблицу одним вертикальным или горизонтальным разрезом, проходящим по сторонам клеток, так чтобы сумма чисел в получившихся частях таблицы отличалась как можно меньше. В этой задаче в одном тесте вам придётся ответить на несколько запросов об оптимальном разрезании таблицы.

Входные данные

В первой строке ввода задано целое число $$$t$$$ — количество запросов ($$$1 \le t \le 10^5$$$).

В следующих $$$t$$$ строках заданы по два числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 10^9$$$, $$$2 \le n \cdot m \le 10^9$$$).

Выходные данные

В $$$t$$$ строках выведите ответы на запросы, по одному на строке.

Ответ на каждый запрос должен быть выведен в формате «D $$$x$$$», где D — это «V», если нужно резать по вертикали, «H» — если по горизонтали, а $$$x$$$ — номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от $$$1$$$ до $$$n$$$, столбцы пронумерованы от $$$1$$$ до $$$m$$$.

Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными $$$x$$$ следует выбрать тот, в котором $$$x$$$ меньше.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
120$$$t = 1$$$, $$$1 \le n, m \le 100$$$полная
214$$$t = 1$$$, $$$1 \le n, m \le 2\,000$$$1первая ошибка
315$$$t = 1$$$, $$$1 \le n, m \le 10^7$$$1, 2первая ошибка
416$$$1 \le t \le 1\,000$$$, $$$1 \le n \times m \le 10\,000$$$1первая ошибка
515$$$1 \le t \le 100\,000$$$, $$$n = 1$$$, $$$1 \le m \le 10^9$$$первая ошибка
620$$$1 \le t \le 100\,000$$$, $$$1 \le n, m \le 10^9$$$1–5первая ошибка
Пример
Входные данные
5
1 3
4 7
1 10
3 3
3 5
Выходные данные
V 3
V 5
V 8
H 3
V 4