GukiZ教授又在玩数组,无意中发现了一个新函数,他称之为GukiZiana。对于给定的数组 a(索引为 1 到 n 的整数)和数字 y,GukiZiana(a, y) 表示 j - i 的最大值,使得 aj = ai = y。如果a中没有y作为元素,那么GukiZiana(a, y)等于- 1。GukiZ还给你准备了一道题。这次,您有两种类型的查询:
1. 第一种类型的形式为 1 l r x 并要求您将所有 ai 的值增加非负整数 x,使得 l ≤ i ≤ r。
2. 第二种类型的形式为 2 y,要求您找到 GukiZiana(a, y) 的值。
对于类型 2 的每个查询,打印答案并让 GukiZ 高兴!
输入
第一行包含两个整数n、q (1 ≤ n ≤ 5 * 105, 1 ≤ q ≤ 5 * 104)、数组a的大小和查询次数。
第二行包含n个整数a1, a2, ... an (1 ≤ ai ≤ 109),构成数组a。
接下来的 q 行包含四个或两个数字,如语句中所述:
如果行以 1 开头,则查询类似于 1 l r x (1 ≤ l ≤ r ≤ n, 0 ≤ x ≤ 109),首先键入查询。
如果行以 2 开头,则第一个查询看起来像 2 y (1 ≤ y ≤ 109),第二类查询。
输出
对于类型 2 的每个查询,打印 GukiZiana(a, y) 的值,作为该查询的 y 值。
示例
输入 #1
4 3 1 2 3 4 1 1 2 1 1 1 1 1 2 3
输出 #1
2
输入 #2
2 3 1 2 1 2 2 1 2 3 2 4
输出 #2
0 -1