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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ t ≤ 10⁵, (1 ≤ n, m ≤ 10⁹, 2 ≤ n ⋅ m ≤ 10⁹)

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

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

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

5
1 3
4 7
1 10
3 3
3 5

V 3
V 5
V 8
H 3
V 4

Разбор

Подзадача 1

Переберем линию разделения. Затем за n ⋅ m посчитаем сумму в разделенной таблице. Выберем лучший разрез. В сумме решение работает за n ⋅ m ⋅ (n + m).

Подзадача 2

Заметим, что при перемещении линии разреза на 1 в каждой из половин добавляется или удаляется только O(n) или O(m) клеток. Значит можно перебрать все варианты за O(nm).

Подзадачи 3 и 4

Зафиксируем какой-нибудь разрез по вертикали перед столбцом k, посчитаем сумму в полученном прямоугольнике, используя сумму арифметической прогрессии:

a₁ + a₂ + a₃ + …  + a_x = (a₁ + a_x)2 ⋅ x

Применяя, получаем: 1 + 2 + …  + k + (m + 1) + (m + 2) + …  + (m + k) + …  + (m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + 2) + …  + (m ⋅ (n − 1) + k) = 

 = 1 + k2 ⋅ k + (m + 1) + (m + k))2 ⋅ k + …  + ((m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + k)2 ⋅ k

Полученная сумма также является арифметической прогрессией с шагом m ⋅ k, значит она равна:

1 + k2 ⋅ k + ((m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + k)2 ⋅ k2 ⋅ n

Сумму в горизонтальном разрезе найдем по более простой формуле:

1 + 2 + …  + m + (m + 1) + (m + 2) + …  + (m + m) + …  + (m ⋅ (k − 1) + 1) + (m ⋅ (k − 1) + 2) + …  + (m ⋅ (k − 1) + m)

1 + m ⋅ k2 ⋅ mk

Таким образом, за O(1) можно посчитать сумму при фиксированном разрезе, а значит, можно найти лучший разрез за (n + m).

Подзадача 5

Здесь арифметическая прогрессия одномерная, и надо найти такое k, чтобы

1 + k2 ⋅ k ≈ 1 + m4 ⋅ m

Решение 1

Упрощая, получим квадратное уравнение на k, и найдем лучшее k за O(1). Из-за округлений возможна погрешность, поэтому нужно перебрать ответ в диапазоне  ± 1.

Решение 2

Можно найти лучшее k, используя двоичный поиск (сумма первых k значений возрастает при увеличении k).

Подзадача 6

Совместим идеи в подзадачах 4 и 5: Посчитаем сумму при фиксированной границе раздела:

1 + k2 ⋅ k + ((m ⋅ (n − 1) + 1) + (m ⋅ (n − 1) + k)2 ⋅ k2 ⋅ n ≈ 1 + n ⋅ m4 ⋅ nm

Решение 1 за O(1) на запрос

Упрощая, получим квадратное уравнение на k, и найдем лучшее k с точностью до  ± 1, так как знак приблизительно равно.

Решение 2 за log₂max(n, m) на запрос

Можно найти лучшее k, используя двоичный поиск, так как значение слева возрастает при увеличении k.