Когда Кевин был в доме БигМена, внезапно ловушка послала его в сетку из $$$n$$$ строк и $$$m$$$ столбцов.

Ловушка Бигмена задается двумя массивами: массивом $$$a_1,a_2,\ldots,a_n$$$ и массивом $$$b_1,b_2,\ldots,b_m$$$.

В $$$i$$$-м ряду находится нагреватель, который нагревает строку на $$$a_i$$$ градусов, а в $$$j$$$-м столбце  — нагреватель, который нагревает столбец на $$$b_j$$$ градусов, так что температура ячейки $$$(i,j)$$$ равна $$$a_i+b_j$$$.

К счастью, у Кевина есть костюм с одним параметром $$$x$$$ и двумя режимами:

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

Как только Кевин приземляется на ячейку, костюм автоматически переходит в режим холодостойкости, если ячейка имеет температуру ниже $$$x$$$, или в режим теплостойкости в противном случае, и не может измениться после этого.

Мы говорим, что две ячейки соседние, если они имеют общую сторону.

Назовем путем последовательность $$$c_1,c_2,\ldots,c_k$$$ ячеек такую, что $$$c_i$$$ и $$$c_{i+1}$$$ соседние для всех $$$1 \leq i \leq k-1$$$.

Скажем, что две ячейки соединены, если между ними есть путь, состоящий только из ячеек, на которые Кевин может наступать.

Связанная компонента  — это максимальный набор попарно связанных ячеек.

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

Чтобы оценить ситуацию, Кевин дает оценку $$$1$$$ каждой хорошей компоненте и $$$2$$$ каждой плохой компоненте.

Итоговой оценкой будет разница между общей оценкой компонент с температурами больше или равными $$$x$$$ и общей оценкой компонентов с температурами меньше $$$x$$$.

Кевин может использовать $$$q$$$ возможных значений $$$x$$$, и для каждого из них Кевин хочет знать итоговую оценку.

Помогите Кевину победить Бигмена!