3116: 守护彩虹岛

有一天彩虹岛的士兵在巡逻，突然发现远方出现了大量军队，貌似要攻占彩虹岛，于是赶紧去和岛主 $lxh$ 报告。由于彩虹岛拥有重量级武器，所以他们并不害怕，但是这个重量级武器需要 $m$ 次操作才能被唤醒，可是由于这个武器很特殊，如果在操作过程中武器的燃料低于极限值，应该立即终止，武器就会报废。武器的燃料定义为：$min(a_i*gcd(a_1,...,a_n))$

唤醒步骤为：

第一步：生成长度为 $n$ 的序列。

第二步：生成 $m$ 个操作步骤。

第三步：按照步骤执行以下操作

操作 $1$：给区间 $[l,r]$ 加上 $x$ ;

操作 $2$：输出以 $l$ 开始，$gcd(a_l,..,a_r) \ge x$ 的最远的 $r$ ($r\ge l$)；答案不存在，输出 $-1$ 。

执行完毕后，武器将会被唤醒，然后就可防御入侵者了。

如果在操作过程中武器的燃料低于极限值，应该立即终止，武器报废——输出 ”Broken"。

第一行为三个整数 $n，m，k$，分别代表序列长度、操作步骤数、极限值。

接下来一行有 $n$ 个整数，用空格分开，表示原始序列 $a_i$。

接下来 $m$ 行，每行一个操作，格式有如下两种：

1. $1 ~ l~r~x$，给区间 $[l,r]$ 加上 $x$ 。
2. $2 ~l~ x$，输出以 $l$ 开始，$gcd(a_l,..,a_r) \ge x$ 的最远的 $r$ ($r\ge l$)，答案不存在输出 $-1$ 。

$1\le n \le100000$，$1\le m\le100000$，$1\le W \le 20$，$1\le l\le r\le n$，$1\le x\le10^9$

对于每一个操作 $2$，输出以 $l$ 开始，$gcd(a_l,..,a_r) \ge x$ 的最远的 $r$ ($r\ge l$)，答案不存在输出 $-1$，占一行。

注意：如果在一个操作完成后，武器燃料值低于极限值，那么直接输出 "Broken"。

2 2 1 
2 1
1 1 2 2 
2 1 1

2