Розглянемо біматричну гру двох гравців.

Напишіть програму, яка за вказаними матрицями виграшів визначить, в яких парах стратегій кожного з гравців одна домінує іншу.

Деяка стратегія №~i~ строго домінує деяку іншу стратегію №~k~ того самого гравця, коли для кожної конкретної стратегії іншого гравця справедливо, що виграш при використанні стратегії №~i~ строго більший, чим при використанні статегії №~k~.

Інакше кажучи: для 1-го гравця, стратегія №~i~ строго домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли ~ \forall j (A_{i,j} > A_{k,j}) ~ (де ~A~ – матриця виграшів 1-го гравця); для 2-го гравця, стратегія №~j~ строго домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли ~ \forall i (B_{i,j} > B_{i,k}) ~ (де ~B~ – матриця виграшів 2-го гравця).

Ще інакше кажучи: для 1-го гравця, стратегія №~i~ строго домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли в матриці виграшів 1-го гравця всі елементи ~i~-го рядка строго більші за відповідні елементи ~k~-го рядка; для 2-го гравця, стратегія №~j~ строго домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли в матриці виграшів 2-го гравця всі елементи ~j~-го стовпчика строго більші за відповідні елементи ~k~-го стовпчика.

Деяка стратегія №~i~ слабко домінує деяку іншу стратегію №~k~ того самого гравця, коли для кожної конкретної стратегії іншого гравця справедливо, що виграш при використанні стратегії №~i~ більший або рівний, чим при використанні статегії №~k~.

Інакше кажучи: для 1-го гравця, стратегія №~i~ слабко домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли ~ \forall j (A_{i,j} \geqslant A_{k,j}) ~ (де ~A~ – матриця виграшів 1-го гравця); для 2-го гравця, стратегія №~j~ слабко домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли ~ \forall i (B_{i,j} \geqslant B_{i,k}) ~ (де ~B~ – матриця виграшів 2-го гравця).

Ще інакше кажучи: для 1-го гравця, стратегія №~i~ слабко домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли в матриці виграшів 1-го гравця всі елементи ~i~-го рядка більші або рівні за відповідні елементи ~k~-го рядка; для 2-го гравця, стратегія №~j~ слабко домінує деяку іншу стратегію №~k~ тоді й тільки тоді, коли в матриці виграшів 2-го гравця всі елементи ~j~-го стовпчика більші або рівні за відповідні елементи ~k~-го стовпчика.

Вхідні дані

У першому рядку через пропуск (пробіл) задано кількість стратегій першого гравця ~N~ (~2\leqslant N\leqslant 12~) та кількість стратегій другого гравця ~M~ (~2\leqslant M\leqslant 12~). Далі йде один порожній рядок. Наступні ~N~ рядків містять матрицю виграшів першого гравця, тобто кожен з цих рядків містить рівно ~M~ чисел, розділених одинарними пропусками (пробілами), причому ~j~-е число ~i~-го рядка являє собою виграш першого гравця у випадку, якщо перший гравець застосує стратегію №~i~, а другий стратегію №~j~. Далі йде один порожній рядок, після якого в аналогічному форматі задано матрицю виграшів другого гравця: теж ~N~ рядків по ~M~ чисел, де ~j~-е число ~i~-го рядка являє собою виграш другого гравця у випадку, якщо перший гравець застосує стратегію №~i~, а другий стратегію №~j~. Всі значення елементів матриць є цілими числами, що не перевищують за модулем (абсолютною величиною) 999.

Результати

Ваша програма повинна вивести спочатку в окремому рядку фразу 1st player, потім всі можливі пари стратегій ~i,\,j~ (при ~i{\neq}j~) першого гравця, де ~i~-а стратегія домінує ~j~-у стратегію. Якщо домінування строге, то фраза в окремому рядку повинна мати вигляд i strictly dominates j; якщо строгого домінування нема, але є слабке домінування, то фраза в окремому рядку повинна мати вигляд i weakly dominates j. Виводити слід без лапок, а замість i та j треба виводити конкретні числа-номери стратегій (вважаючи, що нумерація починається з 1). Всі ці фрази повинні бути відсортовані за зростанням ~i~, а при однакових ~i~ – за зростанням ~j~.

Потім слід вивести окремим рядком фразу 2nd player, а після неї – аналогічні, в такому ж форматі, результати порівнянь стратегій другого гравця.

Приклади

Вхід

3 2
2 4
8 6
2 4
11 12
21 22
31 32

Результат

1st player
1 weakly dominates 3
2 strictly dominates 1
2 strictly dominates 3
3 weakly dominates 1
2nd player
2 strictly dominates 1

Примітки

Зверніть увагу, що якщо дві стратегії (чи ще більше стратегій) завжди (для всіх можливих стратегій іншого гравця) приносять абсолютно однакові виграші, слід вважати, що вони взаємно слабко домінують одна одну, й виводити це; але аналогічні твердження, що кожна стратегія слабко домінує саму себе, слід пропускати.