Вы играете в игру на сетке \(n \times m\), в которой компьютер загадал некоторую клетку \((x, y)\) сетки, а вы должны определить, какую именно.
Для этого вы выберете какое-то \(k\) и какие-то \(k\) клеток \((x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)\), и дадите их компьютеру. В ответ вы получите \(k\) чисел \(b_1,\, b_2, \ldots b_k\), где \(b_i\) — манхэттенское расстояние от \((x_i, y_i)\) до скрытой клетки \((x, y)\) (то есть вы знаете, какое расстояние соответствует какой из \(k\) клеток).
Получив эти \(b_1,\, b_2, \ldots, b_k\), вы должны суметь определить загаданную клетку. Для какого наименьшего \(k\) всегда можно правильно угадать загаданную клетку, независимо от того, какую клетку выберет компьютер?
Напомним, что манхэттенское расстояние между клетками \((a_1, b_1)\) и \((a_2, b_2)\) равно \(|a_1-a_2|+|b_1-b_2|\).
Примечание
В первом наборе входных данных наименьшее такое \(k\) равно \(2\), для него можно выбрать, например, клетки \((1, 1)\) и \((2, 1)\).
Обратите внимание, что для \(k = 2\) нельзя выбрать клетки \((1, 1)\) и \((2, 3)\), так как обе клетки \((1, 2)\) и \((2, 1)\) дадут \(b_1 = 1, b_2 = 2\), поэтому мы не сможем определить, какая клетка скрыта, если компьютер выберет одну из них.
Во втором наборе входных данных следует выбрать \(k = 1\), для него можно выбрать клетку \((3, 1)\) или \((1, 1)\).