← 返回题目列表

Codeforces · 717/F

F. 魔法制作英雄 III

中文机器翻译题面 查看原题

我在阳光下漫步,耶啊!而且感觉不是很好吗!嗯,对于我们的魔法制作英雄来说,这确实感觉很好,他们悠闲地走在单向道路上,与小鬼战斗。小鬼是一种软弱无力的生物,而且他们也不擅长。然而,英雄们喜欢与他们战斗。不说别的,就是为了好玩。

我们的英雄,伊格内修斯,非常喜欢小鬼。他正在观察一行 imps,表示为长度为 n 的整数 a 的零索引数组,其中 ai 表示第 i 个位置处的 imps 数量。有时,小鬼会突然出现。当英雄与小鬼战斗时,他们会选择一条线段,从该线段的一端开始,在另一端结束,而不会退出该线段。它们可以从当前位置向左或向右恰好移动一个单元格,当它们这样做时,它们会击败它们移动到的单元格上的一个小鬼,因此,该单元格上的小鬼数量会减少一个。当英雄出现在路段的一端、他们的行走开始时,这也适用。

他们的目标是击败该段中的所有小鬼,而无需移动到其中的空单元格(没有小鬼),因为他们会感到无聊。由于伊格内修斯喜欢小鬼,他并不是真的想和他们战斗,所以在这个任务的事件中没有小鬼受到伤害。不过,他希望你告诉他,如果他愿意的话,是否可以通过上述方式清除某部分小鬼。

您将收到 q 个查询,其中有两种类型:

- 1 a b k — 表示 k 个 imp 出现在区间 [a, b] 的每个单元格中
- 2 a b - 询问 Ignatius 是否可以按照上述方式击败区间 [a, b] 上的所有小鬼

输入

第一行包含单个整数 n (1 ≤ n ≤ 200 000),即数组 a 的长度。下面一行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 5 000),即每个单元格中 imp 的初始数量。第三行包含一个整数 q (1 ≤ q ≤ 300 000),即查询次数。其余 q 行每行包含一个查询。每个查询由整数 a、b 和可能的 k (0 ≤ a ≤ b < n, 0 ≤ k ≤ 5 000) 提供。

输出

对于每种第二种类型的查询,如果可以清除段,则输出 1,如果不能,则输出 0。

示例

输入 #1

3
2 2 2
3
2 0 2
1 1 1 1
2 0 2

输出 #1

0
1

注意

对于第一个查询,可以轻松检查在清除所有内容的同时确实不可能从第一个单元格到达最后一个单元格。在第二个位置加 1 后,我们可以清除该段,例如通过以下方式移动:$$0 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 0 \rightarrow 1 \rightarrow 2$$。