题目描述

我们称两个字符 $a,b$ 是匹配的，当且仅当 $a=b$ 或 $a,b$ 中至少一个是字符 ?。例如：

• x 和 x 是匹配的；
• x 和 ? 是匹配的；
• ? 和 x 是匹配的；
• ? 和 ? 是匹配的；
• 但 x 和 y 不是匹配的。

我们称两个字符串 $s$ 和 $t$ 是匹配的，当且仅当 $s$ 和 $t$ 长度相同，且对应位置上的字符是匹配的。例如，abc??z 和 a?cx?? 是匹配的。

给定两个字符串 $s,t$，规定 $s(l,r)$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符组成的字符串（$1\leq l\leq r\leq |s|$）。例如：若 $s=\texttt{luogu}$，则 $s(2,4)=\texttt{uog}$。

现在，请你求出所有的 $l,r$，使得 $t$ 和 $s(l,r)$ 匹配。

输入格式

第一行是一个字符串 $s$。

第二行是一个字符串 $t$。

输出格式

输出若干行，每行两个整数，表示一组 $l,r$。

按 $l$ 从小到大的顺序输出。可以证明，按这个顺序进行输出的方案是唯一的。

样例 #1

样例输入 #1

luogu
uog

样例输出 #1

2 4

样例 #2

样例输入 #2

aabbcc
b??

样例输出 #2

3 5
4 6

样例 #3

样例输入 #3

a?b?c?
bcc

样例输出 #3

3 5
4 6

样例 #4

样例输入 #4

a?b?c?
b??

样例输出 #4

2 4
3 5
4 6

提示

数据规模与约定

对全部的测试数据，保证 $1\leq |s|,|t|\leq 10^3$，$|t|\le |s|$，$s,t$ 中只含小写英文字母和字符 ?。