#P0833. 生日快乐

生日快乐

题目描述

雨停了,空气里还带着湿润的香气

午后的阳光照进蛋糕屋

孩子捧着小小的蛋糕,轻声许下心愿

孩子咬下一口蛋糕

生日快乐...

在美食小镇的中央,有一家著名的蛋糕屋。蛋糕屋里有一面长长的货架,从左到右依次摆放着11 号到 nn 号的nn 种蛋糕。每个货架上最初都放着若干块精美的蛋糕。

小镇的居民们很喜欢来这里吃蛋糕,但为了公平,蛋糕屋的店主规定了三条特别的规则:

  1. 买蛋糕:当居民们点单时,他们会选择一个区间[l,r][l, r],店主将从左到右依次走过编号i∈[l,r]i \in [l, r]的每个货架,如果第ii个货架上有蛋糕,店主就拿出一块递给顾客;如果货架已经空了,店主就直接跳过,继续往后走去看下一个货架。
  2. 查看空货架:有时候居民会好奇某个货架的情况,会询问店主一个编号xx,如果第xx号货架上还有蛋糕,店主回答−1-1,表示货架仍然有货;如果第xx号货架已经空了,店主会告诉居民它是当前的所有空货架里,第几个被买空的。
  3. 补货:新一批蛋糕新鲜出炉,店主在第xx个货架上补充一块蛋糕,如果第xx个货架原来是空货架,此操作后他将不空。

输入格式

本题包含多组测试数据。

第一行输入一个整数T(1≤T≤105)T(1 \le T \le 10^5)。

对于每组测试数据,第一行为两个整数n,q(1≤n,q≤105)n, q(1 \le n, q \le 10^5),分别表示蛋糕的种类数、操作的次数。

接下来一行,输入nn个整数a1,a2,...,an(1≤ai≤20)a_1, a_2, ... ,a_n(1 \le a_i \le 20),aia_i表示第ii个货架上蛋糕的初始数量。

接下来qq行,每行先输入一个整数op(1≤op≤3)op(1 \le op \le 3)表示操作类型,随后:

  • 若op=1op = 1,在同一行上输入两个整数l,r(1≤l≤r≤n)l, r(1 \le l \le r \le n),表示按顺序依次买下第ll到第rr个货架上的一块蛋糕。
  • 若op=2op = 2,在同一行上输入一个整数x(1≤x≤n)x(1 \le x \le n),表示一次询问。
  • 若op=3op = 3,在同一行上输入一个整数x(1≤x≤n)x(1 \le x \le n),表示在第xx个货架上再添一块蛋糕。

对于所有测试数据,保证∑n≤105,∑q≤105\sum n \le 10 ^5, \sum q \le 10^5,保证每组测试数据中至少存在一个op=2op = 2的操作。

输出格式

对于每次询问操作,如果货架上没有蛋糕了,输出一行一个整数:对于当前场上所有的空货架,这个货架是其中第几个被买空的;如果货架上还有蛋糕,在一行内输出−1-1。

样例

2
5 9
1 2 3 2 1
1 2 3
1 1 5
2 2
3 1
2 5
3 3
1 2 5
2 3
2 4
5 7
1 1 1 1 1
1 2 3
2 3
1 3 5
2 4
2 1
1 1 5
2 1
2
2
-1
3
2
3
-1
5

提示

对于第一组测试数据:

第一次询问时:货架上蛋糕数量分别为:[0,0,1,1,0][0, 0, 1, 1, 0],当前被买空的货架被买空的先后顺序为:1,2,51, 2, 5。

第二次询问时:货架上蛋糕数量分别为:[1,0,1,1,0][1, 0, 1, 1, 0],当前被买空的货架被买空的先后顺序为:2,52, 5。

第三次、第四次询问时:货架上蛋糕数量分别为:[1,0,1,0,0][1, 0, 1, 0, 0],当前被买空的货架被买空的先后顺序为:2,5,42, 5, 4。