班里有 $N$ 个学生，他们的编号是 $0$ 到 $N-1$。每天，老师都有一些项目需要学生去完成。每个项目都需要由一组学生在一天内完成。项目的难度可能不同。对于每个项目，老师知道该由多少学生组成的小组去完成。

不同的学生对小组的规模有不同的喜好。更准确的说，对学生 $i$ 而言，他只愿意待在人数在 $[A[i],B[i]]$ 内的小组工作。每一天，一个学生最多被分配到一个小组。有些学生可能不被分配到任何一个小组里。每个小组只负责一个项目。

老师已经选择好接下来 $Q$ 天每一天的项目。对于每一天，现需要判断是否有一种分配学生的方案，使得每个项目都有一个小组负责。

样例

现在有 $N=4$ 个学生，且有 $Q=2$ 天。每个学生对于小组规模的喜好如下：

学生 $0$：$A[0]=1,B[0]=2$

学生 $1$：$A[1]=2,B[1]=3$

学生 $2$：$A[2]=2,B[2]=3$

学生 $3$：$A[3]=2,B[3]=4$

第一天有 $M=2$ 个项目，需要的规模分别为 $K[0]=1$ 以及 $K[1]=1$。在这种情况下，没有一种适合学生的方案，因为只有学生 $0$ 愿意参加人数为 $1$ 的小组。

任务

给定对所有学生的描述：$N$, $A$ 以及 $B$ ,同时也给定 $Q$ 个问题的序列 —— 每天一个问题。每个问题包含当天要完成的 $M$ 个项目，同时含有一个长度为 $M$ 的序列 $K$，$K[i]$表示项目 $i$ 所需要的小组人数。对于每个问题，你的程序需要返回是否存在一种小组分配的方案，可以完成当天的所有项目。

你需要实现两个函数，他们分别是 $\mathrm{init}$ 和 $\mathrm{can}$:

• $\mathrm{init}(N,A,B)$---- 测评库在开始时会调用该函数恰好一次。
  • $N$:学生的数目
  • $A$:一个长度为 $N$ 的数组，$A[i]$ 表示学生 $i$ 愿意加入的最少的小组人数
  • $B$:一个长度为 $N$ 的数组，$B[i]$ 表示学生 $i$ 愿意加入的最多的小组人数
  • 这个函数没有返回值
  • 你可以假设 $1\le A[i]\le B[i]\le N$
• $\mathrm{can}(M,K)$ ---当调用完一次 $init$ 后，测评库会连续调用该函数 $Q$ 次表示每一天的询问
  • $M$:当天要完成的项目数
  • $K$:一个长度为 $M$ 的数组，$K[i]$ 表示项目 $i$ 需要的小组规模
  • 如果存在一种分组完成当天的项目，返回 $1$，否则返回 $0$
  • 你可以假设 $1\le M\le N,1\le K[i]\le N$。注意:$K[i]$ 之和可能大于 $N$

注意：不知道为什么，IOI 的官方数据存在 $M>N$ 的数据，但是保证 $M\le 200000$，请UOJ的用户在做的时候注意下

子任务

假设 $S$ 表示调用的 $\mathrm{can}(M,K)$ 的 $M$ 的总和。

样例测评库

样例测评库将以下面的格式读入相关数据:

• 第一行：$N$
• 第 $2,\dots ,N+1$ 行：$A[i]$ $B[i]$
• 第 $N+2$ 行：$Q$
• 第 $N+3,\dots ,N+Q+2$ 行：$M$ $K[0]$ $K[1]$ $\dots$ $K[M-1]$

对于每个问题，样例测评库都会输出函数 $\mathrm{can}$ 的返回值

交互式类型的题目怎么本地测试

时间限制：$4\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$

下载

样例及测评库下载