题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$，以及一个长度为 $N-1$ 的整数序列 $P=(P_2,\cdots,P_N)$。请注意，$P$ 的下标从 $2$ 开始。此外，保证 $1\leq P_i < i$。

你需要重复以下操作 $10^{100}$ 次：

• 对于每个 $i=2,\cdots,N$，按顺序将 $A_{P_i}$ 的值替换为 $A_{P_i}+A_i$。

请判断所有操作结束后，$A_1$ 是正数、负数还是 $0$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $P_2$ $\cdots$ $P_N$

输出格式

如果所有操作结束后 $A_1$ 为正数，输出 +；为负数，输出 -；为 $0$，输出 0。

样例 1

输入

4
1 -2 3 -4
1 2 3

输出

-

样例 2

输入

3
0 1 -1
1 1

输出

0

样例 3

输入

5
1 -1 1 -1 1
1 1 2 2

输出

+

样例 4

输入

20
568273618 939017124 -32990462 -906026662 403558381 -811698210 56805591 0 436005733 -303345804 96409976 179069924 0 0 0 -626752087 569946496 0 0 0
1 1 1 4 4 6 7 2 2 3 3 8 13 14 9 9 15 18 19

输出

+

说明/提示

限制条件

• $2\leq N\leq 250000$
• $-10^9\leq A_i\leq 10^9$
• $1\leq P_i < i$
• 所有输入值均为整数。

样例解释 1

以下展示了最初几次操作的结果。

• 第 $1$ 次操作
  • 操作前：$A=(1,-2,3,-4)$
  • 对 $i=2$ 处理：将 $A_1$ 替换为 $A_1+A_2=1+(-2)=-1$
  • 对 $i=3$ 处理：将 $A_2$ 替换为 $A_2+A_3=-2+3=1$
  • 对 $i=4$ 处理：将 $A_3$ 替换为 $A_3+A_4=3+(-4)=-1$
  • 操作后：$A=(-1,1,-1,-4)$
• 第 $2$ 次操作后，$A=(0,0,-5,-4)$
• 第 $3$ 次操作后，$A=(0,-5,-9,-4)$
• 第 $4$ 次操作后，$A=(-5,-14,-13,-4)$
• $\vdots$
• 重复操作 $10^{100}$ 次后，$A_1$ 会变为负数。

因此，应输出 -。

由 ChatGPT 4.1 翻译