Time limit 2000/2000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Binary string is any sequence of two digits 0 and 1. The simplest binary transformation of binary string S is defined with two numbers l and r (1 <= l <= r <= |S|, where |S| is length of S). This binary transfomation changes all digits of S starting from index l to index r from 0 to 1 and form 1 to 0 (e.g. if S = '10101' , l=2, r=4 then after transformation S = '11011').
You are given two binary strings A and B. Find the shortest way to transform first to the second using binary transformations.
Input
On the first line there is one number N (1 <= N <= 30000) length of binary strings below. On the second line there is binary string A, and binary string B is on the third line. |A| = |B| = N.
Output
On the first line write K - smallest number of transformations required. On the next K lines write values of li and ri for each transformation.
Example
| stdin |
stdout |
3
010
111
|
2
1 1
3 3
|
6
000111
000000
|
1
4 6
|
Для отправки решений необходимо выполнить вход.
|