Майстер побиття шашок

Обмеження: 2 сек., 512 МіБ

Зенику стало нудно на роботі, тож він вигадав собі наступну задачу. Є шахова дошка розміру \(n \times m\) і необмежена кількість шашок білого кольору та одна шашка чорного кольору. Він хоче розставити якомога більше шашок білого кольору так, щоб можна було поставити одну чорну шашку і побити усі білі шашки за один хід. Одним ходом вважатимемо такий процес:

• Якщо перед чорною шашкою по діагоналі (у будь-якому із чотирьох напрямів) стоїть шашка протилежного кольору, а наступна за нею клітинка вільна, то шашка може перестрибнути через шашку суперника. Шашку, через яку перестрибнули, знімають з дошки та вважають побитою.

• Перестрибнувши одну шашку, шашка може перестрибувати далі (можливо, в інших діагональних напрямках), якщо є така можливість.

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

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(m\) — розміри дошки.

У другому рядку дано рядок \(s\), який рівний Yes або No і вказує, чи потрібно виводити розміщення шашок та ходи.

Вихідні дані

У першому рядку виведіть одне ціле число \(c\) — максимальну кількість білих шашок, що можна поставити на дошці.

Якщо рядок \(s\) рівний No, то більше нічого не потрібно виводити. Якщо ж він рівний Yes, то:

У наступних \(c\) рядках виведіть по два натуральні числа \(wx_i, wy_i\) (номер рядка та номер стовпця, розділених пробілом) — розташування білих шашок.

У наступному рядку виведіть два натуральні числа \(bx_0, by_0\) — початкове розташування чорної шашки.

У наступних \(c\) рядках виведіть по два натуральні числа \(bx_i, by_i\) — розташування чорної шашки після кожного наступного зробленого ходу.

Якщо правильних відповідей є декілька, дозволено вивести будь-яку із них.

Обмеження

\(1 \le n \cdot m \le 10^5\),

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 8 балів: \(n \le 2\), \(s =\) No,

• 14 балів: \(n = 3\), \(s =\) No,

• 25 балів: \(n \cdot m \le 10^5\), \(s =\) No,

• 18 балів: \(n, m \le 10\), \(s =\) Yes,

• 20 балів: \(n \% 4 = m \% 4 = 1\), \(s =\) Yes,

• 13 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 No	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 3 Yes	2 4 2 2 2 1 3 3 1 5 3

Примітки

Один із варіантів розташування шашок та ходів чорною шашкою у другому прикладі: