有两个字符串 s 和 t,仅由字母 a 和 b 组成。您可以多次进行以下操作:选择 s 前缀、t 前缀并交换它们。前缀可以为空,也可以与整个字符串一致。
你的任务是找到一系列操作,其中一个字符串仅包含 a 字母,另一个字符串仅包含 b 字母。应尽量减少操作次数。
输入
第一行包含字符串 s (1 ≤ |s| ≤ 2·105)。
第二行包含字符串 t (1 ≤ |t| ≤ 2·105)。
这里|s|和|t|分别表示 s 和 t 的长度。保证至少一个字符串包含至少一个a字母并且至少一个字符串包含至少一个b字母。
输出
第一行应包含一个整数 n (0 ≤ n ≤ 5·105) - 操作数。
接下来的 n 行中的每一行都应包含两个以空格分隔的整数 ai、bi - 分别是要交换的 s 和 t 的前缀长度。
如果有多种可能的解决方案,您可以打印其中任何一个。保证存在给定约束的解决方案。
示例
输入 #1
bab bb
输出 #1
2 1 0 1 3
输入 #2
bbbb aaa
输出 #2
0
注意
在第一个示例中,您可以通过两个操作来解决问题:
1. 交换第一个长度为 1 的字符串的前缀和第二个长度为 0 的字符串的前缀。交换后,您将得到字符串 ab 和 bbb。
2. 交换第一个长度为 1 的字符串的前缀和第二个长度为 3 的字符串的前缀。交换后,您将得到字符串 bbbb 和 a。
在第二个示例中,字符串已经合适,因此不需要任何操作。