题目描述

给定一个 $n$ 个点的树，$1$ 为根。每一个树上的点 $u$ 都对应一个平面上的点的集合 $S_u$。对于叶子 $l$，有 $|S_l|=1$，即每个叶子对应的点集都只包含一个点。所有叶子的点集 $S$ 给定。

非叶子节点分为 A、B 两类，其中：

• 对于 A 类点 $u$，满足 $S_u$ 为 $u$ 的所有孩子 $v$ 的 $S_v$ 的并，保留严格上凸壳（即，不会有三点共线）；
  • 形式化地说，设所有孩子 $v$ 的 $S_v$ 的并为 $S$，则 $S_u$ 中的任意点 $(x,y)$ 均满足：
    • $(x,y)\in S$；
    • 不存在两个点 $(x_1,y_1),(x_2,y_2)\in S$，使得 $x_1<x<x_2$，且 $(x,y)$ 在 $(x_1,y_1),(x_2,y_2)$ 连线上，或在 $(x_1,y_1),(x_2,y_2)$ 连线下方。
• 对于 B 类点 $u$，满足 $S_u$ 为 $u$ 的所有孩子 $v$ 的 $S_v$ 的并，保留严格下凸壳。
  • 形式化地说，设所有孩子 $v$ 的 $S_v$ 的并为 $S$，则 $S_u$ 中的任意点 $(x,y)$ 均满足：
    • $(x,y)\in S$；
    • 不存在两个点 $(x_1,y_1),(x_2,y_2)\in S$，使得 $x_1<x<x_2$，且 $(x,y)$ 在 $(x_1,y_1),(x_2,y_2)$ 连线上，或在 $(x_1,y_1),(x_2,y_2)$ 连线上方。

给定 $q$ 次询问，每次询问给定一个叶子 $x$，判断是否可以指定每一个非叶子节点为 A/B 类，使得 $S_x$ 中的点出现在 $S_1$ 中。

输入格式

从文件 $\textit{rgn.in}$ 中读入数据。

单测试点包含多组数据，第一行两个整数 $id,T$ 分别表示子任务编号和数据组数。对于样例，$id$ 代表该样例满足子任务 $id$ 的限制。

对于每组数据：

第一行两个整数 $n,q$。

接下来一行 $n-1$ 个空格分隔的数，第 $i$ 个数表示节点 $i+1$ 在树上的父亲 $f_{i+1}$。

接下来若干行，每行两个整数 $x,y$，按照编号从小到大给出所有叶子对应的平面点的坐标。

接下来 $q$ 行，每行输入一个 $u$，表示询问的节点的编号。保证树上 $u$ 是叶子。

输出格式

输出到文件 $\textit{rgn.out}$ 中。

对于每组数据输出一行一个长度为 $q$ 的 0/1 串，对于第 $i$ 个询问，如果存在一种合法的指定每个节点是 A/B 类的方案使得要求的点出现在 $S_1$ 内，则第 $i$ 个字符应为 1；否则应为 0。

样例 #1

样例输入 #1

1 1
5 3
1 1 2 2
1 3
2 5
3 6
3
4
5

样例输出 #1

111

叶子编号从小到大分别为 $3,4,5$，因此 $S_3=\{(1,3)\},S_4=\{(2,5)\},S_5=\{(3,6)\}$。

树上所有非叶子节点均设定为 A 类点时，$S_2=\{(2,5),(3,6)\},S_1=\{(1,3),(2,5),(3,6)\}$，包含所有的三个点。

样例 #2 ~ #5

见下发文件中的 $\textit{rgn/rgn[2-5].in}$ 与 $\textit{rgn/rgn[2-5].ans}$。

提示

对于 $100\%$ 的数据，满足 $1\leq T\leq 10^5$，$3\leq n\leq 3\times 10^5$，$1\leq q\leq n$，$\sum n\leq 5\times 10^5$，$1\leq x,y\leq 10^9$，$1\leq f_i<i$，所有点 $x$ 坐标互不相同。

评测时开启合理的子任务依赖，每个子任务分值均为 $10$ 分。