Задача . E2. Игра Подугольник (сложная версия)

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

Цовак и Нарек играют в игру. У них есть массив \(a\) и матрица целых чисел \(b\) с \(n\) строками и \(m\) столбцами, пронумерованных с \(1\). Ячейка в \(i\)-й строке и \(j\)-м столбце обозначается \((i, j)\).

Они ищут элементы \(a\) по очереди; первым начинает Цовак. Каждый раз игрок ищет в матрице клетку, содержащую текущий элемент \(a\) (Цовак ищет первый, Нарек — второй и т.д.). Допустим, игрок выбрал клетку \((r, c)\). Следующий игрок должен выбрать свою клетку в подматрице, начинающейся в \((r + 1, c + 1)\) и заканчивающейся в \((n, m)\) (подматрица может быть пустой, если \(r=n\) или \(c=m\)). Если игрок не может найти такую клетку (или оставшаяся подматрица пуста) или массив заканчивается (предыдущий игрок выбрал последний элемент), то он проигрывает.

Ваша задача — определить победителя, если игроки играют оптимально.

Примечание: поскольку входные данные велики, вам может потребоваться оптимизация ввода/вывода для этой задачи.

Например, в C++ достаточно использовать следующие строки в начале функции main():

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}