E. Выпуклая игра
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Шикамару и Асума любят играть в различные игры, и очень часто они играют в следующую игру. У них есть список возрастающих чисел, и они по очереди делают ходы. Каждый ход — это выбор числа из списка. Пусть в процессе игры последовательно были выбраны числа $$$v_{i_1}$$$, $$$v_{i_2}$$$, $$$\ldots$$$, $$$v_{i_k}$$$. Числа должны удовлетворять следующим правилам:

  • $$$i_{j} < i_{j+1}$$$, если $$$1 \leq j \leq k-1$$$;
  • $$$v_{i_{j+1}} - v_{i_j} < v_{i_{j+2}} - v_{i_{j+1}}$$$, если $$$1 \leq j \leq k-2$$$.

Но поскольку играть в одну игру просто, то сегодня Шикамару и Асума решили сыграть в $$$n$$$ игр одновременно. Они договорились, что ходить они также будут по очереди, причем начинает Шикамару. Делать ход разрешается в любой из игр, где это еще возможно. Проигрывает тот, кто не может сделать ход ни в одной из игр. Необходимо определить, кто выиграет при оптимальной игре обоих игроков.

Входные данные

В первой строке дано число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — количество игр. В следующих строках содержатся описания игр.

В первой строке описания каждой игры содержится число $$$m$$$ ($$$m\geq 1$$$) — количество чисел в игре.

В следующей строке содержится последовательность целых чисел $$$v_1$$$, $$$v_2$$$, ..., $$$v_m$$$ через пробел ($$$1 \leq v_{1} < v_{2} < ... < v_{m} \leq 10^{5}$$$).

Сумма длин последовательностей во всех играх не превосходит $$$10^5$$$.

Выходные данные

Необходимо вывести «YES», если Шикамару может выиграть при оптимальной игре, и «NO» иначе.

Примеры
Входные данные
1
10
1 2 3 4 5 6 7 8 9 10
Выходные данные
YES
Входные данные
2
10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
Выходные данные
NO
Входные данные
4
7
14404 32906 41661 47694 51605 75933 80826
5
25374 42550 60164 62649 86273
2
7002 36731
8
23305 45601 46404 47346 47675 58125 74092 87225
Выходные данные
NO
Примечание

В первом примере Шикамару может сделать ход в последнее число. Тогда Асума не сможет сделать ход из-за первого условия и проиграет.

Во втором примере куда бы ни делал ход Шикамару, Асума всегда может сделать такой же ход в другой игре, поэтому Асума выиграет.