#1903. Chocological

    ID: 1903 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1961来源:qoj.ac数据:公开样例模拟

Chocological

Chocological

题目描述

标题: Chocological - Problem - QOJ.ac

#10301. Chocological

Statistics

有一个 2×n 网格,第 i 行第 j 列的格子记为 (i,j) (1≤i≤2, 1≤j≤n),其中一些格子上存在一个人。

每次操作,你可以从下列选项中选择其一:

  • 选择一行 i,然后令该行所有人左对齐,即若原来第 i 行有 x 个人,则将这一行有人的格子修改为所有的 (i,j) (1≤j≤x)。
  • 选择一行 i,然后令该行所有人右对齐,即若原来第 i 行有 x 个人,则将这一行有人的格子修改为所有的 (i,n−j+1) (1≤j≤x)。
  • 选择一列 j,然后令该行所有人上对齐,即若原来第 j 列有 x 个人,则将这一行有人的格子修改为所有的 (i,j) (1≤i≤x)。
  • 选择一列 j,然后令该行所有人下对齐,即若原来第 j 列有 x 个人,则将这一行有人的格子修改为所有的 (2−i+1,j) (1≤i≤x)。

给定初始状态和最终状态(即每个格子上是否有人,保证总人数相同),判断是否可以通过不超过 106 次操作从初始状态转移到最终状态。如果可以,请给出一种方案。

输入格式

第一行:一个整数 n。

第二行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当初始状态 (1,j) 有人。

第三行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当初始状态 (2,j) 有人。

第四行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当最终状态 (1,j) 有人。

第五行:一个长度为 n 的 01 串,其中第 j 个字符为 1 当且仅当最终状态 (2,j) 有人。

输出格式

若无解,输出 NO。

否则,输出 YES,然后:

第一行:一个整数 m,表示操作数量,你需要保证 0≤m≤106。

接下来 m 行:每行两个整数,分别为操作编号(按照题面书写顺序分别为 1,2,3,4)和操作的行/列编号。

样例

输入

6
010100
110001
010001
100011

输出

YES
3
2 1
3 2
4 5

样例

输入

6
000100
000000
001000
000000

输出

NO

子任务

对于全部数据:1≤n≤105。

Subtask 1 (2%):保证无解。

Subtask 2 (13%):n≤10。

Subtask 3 (15%):人数不超过 10。

Subtask 4 (20%):保证有解。

Subtask 5 (10%):人数不超过 n,且初始状态中第 j 个人的位置为 (1,j)。

Subtask 6 (20%):人数不超过 n。

Subtask 7 (20%):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6
010100
110001
010001
100011
YES
3
2 1
3 2
4 5

样例 2

6
000100
000000
001000
000000
NO