题目描述

Yan 的生日快到了，他想举办一场最有趣的派对。为此，他邀请了自己最喜欢的 $N$ 个朋友，并买了 $N$ 台糖果机。

最开始，Yan 把这 $N$ 个孩子排成一列，并给每个孩子分配一台糖果机。每个孩子事先告诉 Yan 自己想吃多少颗糖，记为 $a_i$；而由于这些糖果机是糖果工厂旅游商店里最后剩下的货，每台机器的容量互不相同，第 $i$ 台机器最多可以提供 $b_i$ 颗糖。

Yan 开始思考各种派对配置。他关心哪些孩子区间 $[l,r]$ 是有效的。我们称区间 $[l,r]$ 有效，当且仅当选出编号满足 $l \le i \le r$ 的孩子后，每个孩子都能吃到至少自己想要的糖果数。

由于直接满足这一条件往往不可能，Yan 决定允许每个孩子从两台机器中取糖：

• 自己的机器；
• 左边那个孩子的机器。

对于区间中最左边的孩子，他允许其从该区间最右边孩子的机器中取糖。也就是说，在区间内部形成了一个闭环，每个孩子都恰好可以从两台机器中取糖。

注意：

• 孩子之间不能互相传递糖果；
• 也不能从区间外的机器中取糖。

随着时间推移，孩子们会改变自己的想法。每次变化都对应一个四元组 $(l,r,x,y)$：

• 对所有满足 $l \le i \le r$ 的孩子，将其期望糖果数改为 $x$；
• 同时，Yan 把这些孩子手中的机器全部更换为容量为 $y$ 的机器。

请你帮助 Yan 在所有更新发生后，回答区间是否有效。

任务要求

你需要编写程序 candies，实现以下函数：

• init
• isValid
• update

这些函数会与评测程序一起编译并通信。

每次调用 isValid 时，你都需要基于：

• 初始的孩子需求与机器容量；
• 以及此前所有 update 操作造成的修改；

正确判断给定区间是否有效。

实现细节

你需要实现的初始化函数为：

void init(std::vector<int> kids, const std::vector<int> candies);

该函数只会被调用一次。参数含义如下：

• kids[i]：第 $i$ 个孩子想吃的糖果数；
• candies[i]：最初分给第 $i$ 个孩子的糖果机容量。

之后，评测程序会以任意顺序总共调用下面两个函数 $Q$ 次：

bool isValid(int l, int r);
void update(int l, int r, int x, int y);

其中：

• update(l, r, x, y) 表示对区间 $[l,r]$ 内所有孩子执行修改：
  • 想吃的糖果数都变为 $x$
  • 糖果机容量都变为 $y$
• isValid(l, r) 要求你判断当前区间 $[l,r]$ 是否有效。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $0 \le a_i, b_i, x, y \le 10^9$

子任务

只有当某个子任务的所有测试点全部通过时，才能获得该子任务分数。

本地测试

题目提供了文件 Lgrader.cpp，你可以将其与你的程序一起编译进行本地测试。

本地 grader 的输入格式如下：

• 第一行输入 $N$
• 第二行输入 $N$ 个整数，表示数组 $a_i$
• 第三行输入 $N$ 个整数，表示数组 $b_i$
• 第四行输入 $Q$
• 接下来 $Q$ 行，每行格式为以下两种之一：
  • 1 l r：表示一次 isValid(l, r) 查询
  • 2 l r x y：表示一次 update(l, r, x, y) 操作

程序会输出若干行 0/1，分别对应各次 isValid 查询的结果。

样例

输入

5
2 0 9 4 1
0 5 4 6 7
7
2 4 4 8 1
1 0 1
2 3 3 4 9
2 1 2 2 2
1 3 4
1 2 2
1 2 4

输出

1
0
1