题目描述

给定一个正整数序列 $A$ 和一个定值 $k$。

求其子序列 $A{l\cdots r}$，使得 $\gcd(A{l\cdots r})\cdot(Al\ \mathrm{xor} \ A{l+1}\ \mathrm{xor} \cdots \mathrm{xor} \ A_r)=k$。若无解，输出 no solution。

输入格式

第一行一个整数 $n$，表示 $A$ 的长度。
第二行 $n$ 个整数 $A_{1\cdots n}$。
第三行一个整数 $k$。

输出格式

输出两个整数 $l,r$ 表示答案，如果答案不唯一，输出字典序最小的一个。

样例

input

5
2 4 6 8 10
20

output

2 4

数据范围与提示

$n\leq10^5,a_i\leq 10^{12},k\leq 10^{18}$。

这题解法挺多，如果瞬间水过就下载附加文件看看题解吧

P.S. 这是原题，我只是一个搬运工。