#P17941. Sakura no Mahou

Sakura no Mahou

Sakura no Mahou

有两列长度为 nn 的整数 a1,…,ana_1,\ldots,a_n 和 b1,…,bnb_1,\ldots,b_n,初始元素均为 00 或 11。

一次操作选择一个连续区间 [l,r][l,r],将区间内每个 aia_i 同时改为本次操作前的区间前缀和:

$$a_i\leftarrow\sum_{j=l}^{i}a_j\qquad(l\le i\le r).$$

每天可以执行任意多次操作,但同一天所选区间必须两两不相交。求使所有位置满足 ai≡bi(mod2)a_i\equiv b_i\pmod2 的最少天数,并输出一种达到最少天数的操作方案。如果不可能,报告无解。

输入格式

第一行是测试用例数 tt,1≤t≤250001\le t\le25000。

每组用例第一行包含 nn。第二行和第三行分别包含 nn 个整数,给出 aa 和 bb。

1≤n≤10001\le n\le1000,ai,bi∈{0,1}a_i,b_i\in\{0,1\};所有用例的 ∑n2≤106\sum n^2\le10^6。

输出格式

无解时,对该组用例输出 -1。

否则先输出最少天数 kk。接下来 kk 行,第 ii 行输出

$$c_i\ l_{i,1}\ r_{i,1}\ l_{i,2}\ r_{i,2}\ \cdots\ l_{i,c_i}\ r_{i,c_i},$$

表示第 ii 天的 cic_i 个操作区间。必须满足 1≤li,j≤ri,j≤n1\le l_{i,j}\le r_{i,j}\le n,且相邻区间满足 ri,j<li,j+1r_{i,j}<l_{i,j+1}。当天不操作时可输出 ci=0c_i=0。

若初始已符合要求,输出 k=0k=0,不用再输出操作。最优方案不唯一时输出任意一种。

样例 1

3
5
1 0 1 0 1
0 1 0 1 0
3
1 1 0
1 1 1
10
1 0 0 1 0 1 0 0 1 0
1 0 1 0 0 1 0 1 0 0
-1
1
1 2 3
2
2 1 4 6 9
2 1 2 6 7