Когда Кевин был в доме БигМена, внезапно ловушка послала его в сетку из \(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\), и для каждого из них Кевин хочет знать итоговую оценку.
Помогите Кевину победить Бигмена!