Задача 2. Разбиение таблицы

Автор:Даниил Орешников   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

12345
678910
1112131415

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

Формат входных данных

В первой строке ввода задано целое число t — количество запросов.

В следующих t строках заданы по два целых числа n, m.

Формат выходных данных

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

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

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

Ограничения

1 ≤ t ≤ 105, (1 ≤ n, m ≤ 109, 2 ≤ n ⋅ m ≤ 109)

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

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
120t = 1, 1 ≤ n, m ≤ 100полная
214t = 1, 1 ≤ n, m ≤ 2 0001первая ошибка
315t = 1, 1 ≤ n, m ≤ 1071, 2первая ошибка
4161 ≤ t ≤ 1 000, 1 ≤ n × m ≤ 10 0001первая ошибка
5151 ≤ t ≤ 100 000, n = 1, 1 ≤ m ≤ 109первая ошибка
6201 ≤ t ≤ 100 000, 1 ≤ n, m ≤ 1091 — 5первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
5
1 3
4 7
1 10
3 3
3 5
V 3
V 5
V 8
H 3
V 4

0.187s 0.095s 13