A - Please Sign
Source: atcoder
Difficulty: 400

Problem Statement
You are given an integer sequence
A=(A_1,A_2,\cdots,A_N)
of length
N
, and another integer sequence
P=(P_2,\cdots,P_N)
of length
N-1
. Note that the index of
P
starts at
2
. It is guaranteed that
1 \leq P_i < i
for each
i
.
You will now repeat the following operation
10^{100}
times.
For each
i=2,\cdots,N
, in this order, replace the value of
A_{P_i}
with
A_{P_i}+A_{i}
.
Determine whether
A_1
will be positive, negative, or zero when all operations are completed.
Constraints
2 \leq N \leq 250000
-10^9 \leq A_i \leq 10^9
1 \leq P_i < i
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1
A_2
\cdots
A_N
P_2
\cdots
P_N
Output
If
A_1
is positive when all operations are completed, print
+
; if it is negative, print
-
; if it is zero, print
0
.
Sample Input 1
4
1 -2 3 -4
1 2 3
Sample Output 1
-
Shown below are the results of the first few operations.
After the first operation:
Before the operation:
A=(1,-2,3,-4)
.
Processing for
i=2
: Replace the value of
A_1
with
A_1+A_2=1+(-2)=-1
.
Processing for
i=3
: Replace the value of
A_2
with
A_2+A_3=-2+3=1
.
Processing for
i=4
: Replace the value of
A_3
with
A_3+A_4=3+(-4)=-1
.
After the operation:
A=(-1,1,-1,-4)
.
After the second operation,
A=(0,0,-5,-4)
.
After the third operation,
A=(0,-5,-9,-4)
.
After the fourth operation,
A=(-5,-14,-13,-4)
.
\vdots
After
10^{100}
operations,
A_1
will be negative.
Thus, you should print
-
.
Sample Input 2
3
0 1 -1
1 1
Sample Output 2
0
Sample Input 3
5
1 -1 1 -1 1
1 1 2 2
Sample Output 3
+
Sample Input 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
Sample Output 4
+

C++ solution:
// https://atcoder.jp/contests/arc169/tasks/arc169_a
// 2025年04月25日 20時30分12秒
#include <bits/stdc++.h>
// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint998244353;
// using mint = modint1000000007;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, n) for (long long int i = 0; i < (n); ++i)
#define rep2(i, k, n) for (long long int i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
using vint = vector<int>;
using vll = vector<ll>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<ll>>;

// const ll INF = (ll)2e18+9;
const int INF = (int)2e9 + 7;

template <typename T>
void chmin(T& a, T b) {
    a = min(a, b);
}
template <typename T>
void chmax(T& a, T b) {
    a = max(a, b);
}

template <typename T>
void print(vector<T> v) {
    int n = v.size();
    rep(i, n) {
        if (i == 0)
            cout << v[i];
        else
            cout << ' ' << v[i];
    }
    cout << endl;
}

void yesno(bool x) {
    cout << (x ? "Yes" : "No") << '\n';
}

void solve();

int main() {
    solve();
    return 0;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll A(N + 1);
    rep2(i, 1, N + 1) cin >> A[i];
    vint depth(N + 1);
    vll B(N + 1);
    B[0] = A[1];
    rep2(i, 2, N + 1) {
        int p;
        cin >> p;
        depth[i] = depth[p] + 1;
        B[depth[i]] += A[i];
    }

    string ans = "0";
    for (int i = N; i >= 0; i--) {
        if (B[i] == 0)
            continue;
        if (B[i] > 0)
            ans = "+";
        if (B[i] < 0)
            ans = "-";
        break;
    }
    cout << ans << endl;
}

Go solution:
package main

import (
	"bufio"
	"container/heap"
	"container/list"
	"fmt"
	"os"
	"sort"
	"strconv"
	// "github.com/emirpasic/gods/trees/redblacktree"
)

// const mod = 1000000007

const mod = 998244353

var sc = bufio.NewScanner(os.Stdin)

func main() {
	buf := make([]byte, bufio.MaxScanTokenSize)
	sc.Buffer(buf, 1000*1000)
	sc.Split(bufio.ScanWords)

	n := ni()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = ni()
	}
	dist := make([]int, n)
	for i := 1; i < n; i++ {
		dist[i] = dist[ni()-1]+1
	}

	// distは一番大きくてもn-1
	c := make([]int, n)
	for i:=1; i<n; i++ {
		c[dist[i]] += a[i]
	}
	for i:=n-1; i>0; i-- {
		if c[i] > 0 {
			fmt.Println("+")
			return
		} else if c[i] < 0 {
			fmt.Println("-")
			return
		}
	}

	sum := a[0]
	// for i:=1; i<n; i++ {
	// 	sum -= (dist[i]-1)*a[i]
	// }
	
	if sum > 0 {
		fmt.Println("+")
	} else if sum < 0 {
		fmt.Println("-")
	} else {
		fmt.Println("0")
	}
}

// ==================================================
// io
// ==================================================

func ni() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nf() float64 {
	sc.Scan()
	f, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func ns() string {
	sc.Scan()
	return sc.Text()
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

// ==================================================
// math
// ==================================================
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func chmin(a *int, b int) {
	if *a > b {
		*a = b
	}
}
func chmax(a *int, b int) {
	if *a < b {
		*a = b
	}
}
func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func maxf(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}
func minf(a, b float64) float64 {
	if a < b {
		return a
	}
	return b
}
func chminf(a *float64, b float64) {
	if *a > b {
		*a = b
	}
}
func chmaxf(a *float64, b float64) {
	if *a < b {
		*a = b
	}
}
func absf(a float64) float64 {
	if a > 0 {
		return a
	}
	return -a
}

func pow(x, y int) int {
	// return int(math.Pow(float64(x), float64(y)))
	return mpow(x, y, mod)
}

// ==================================================
// sort
// ==================================================

func sorti(sl []int) {
	sort.Sort(sort.IntSlice(sl))
}

func sortir(sl []int) {
	sort.Sort(sort.Reverse(sort.IntSlice(sl)))
}

func sorts(sl []string) {
	sort.Slice(sl, func(i, j int) bool {
		return sl[i] < sl[j]
	})
}

// ==================================================
// slice
// ==================================================

func initslice(len int, def int) []int {
	sl := make([]int, len)
	for i := 0; i < len; i++ {
		sl[i] = def
	}
	return sl
}

func initslice2(x, y int, def int) [][]int {
	sl := make([][]int, x)
	for i := 0; i < x; i++ {
		sl[i] = initslice(y, def)
	}
	return sl
}

// ==================================================
// mod
// ==================================================
func madd(a, b int) int {
	a += b
	if a >= mod || a <= -mod {
		a %= mod
	}
	if a < 0 {
		a += mod
	}
	return a
}

func mmul(a, b int) int {
	return a * b % mod
}

func mdiv(a, b int) int {
	a %= mod
	return a * minvfermat(b, mod) % mod
}

func mpow(a, n, m int) int {
	if m == 1 {
		return 0
	}
	r := 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % m
		}
		a, n = a*a%m, n>>1
	}
	return r
}

func minv(a, m int) int {
	p, x, u := m, 1, 0
	for p != 0 {
		t := a / p
		a, p = p, a-t*p
		x, u = u, x-t*u
	}
	x %= m
	if x < 0 {
		x += m
	}
	return x
}

// m only allow prime number
func minvfermat(a, m int) int {
	return mpow(a, m-2, mod)
}

// ==================================================
// union find
// ==================================================

type UnionFind struct {
	par []int
}

/*
// 使い方
// インスタンスの生成
u := newUnionFind(N)

// 各メソッドの利用
u.unite(a, b)
u.same(a, b)
u.size(a)
u.root(a)
*/
func newUnionFind(N int) *UnionFind {
	u := new(UnionFind)
	u.par = make([]int, N)
	for i := range u.par {
		u.par[i] = -1
	}
	return u
}

/* xの所属するグループを返す */
func (u UnionFind) root(x int) int {
	if u.par[x] < 0 {
		return x
	}
	u.par[x] = u.root(u.par[x])
	return u.par[x]
}

/* xの所属するグループ と yの所属するグループ を合体する */
func (u UnionFind) unite(x, y int) {
	xr := u.root(x)
	yr := u.root(y)
	if xr == yr {
		return
	}
	u.par[yr] += u.par[xr]
	u.par[xr] = yr
}

/* xとyが同じグループに所属するかどうかを返す */
func (u UnionFind) same(x, y int) bool {
	if u.root(x) == u.root(y) {
		return true
	}
	return false
}

/* xの所属するグループの木の大きさを返す */
func (u UnionFind) size(x int) int {
	return -u.par[u.root(x)]
}

// ==================================================
// binarysearch
// ==================================================

/*
	o = bs(0, len(sl)-1, func(c int) bool {
		return true
	})

sort.Search(n int, func(i int) bool) でも同じことができる
*/
func bs(ok, ng int, f func(int) bool) int {
	if !f(ok) {
		return -1
	}
	if f(ng) {
		return ng
	}
	for abs(ok-ng) > 1 {
		mid := (ok + ng) / 2

		if f(mid) {
			ok = mid
		} else {
			ng = mid
		}
	}

	return ok
}

// ex) 降順のsliceから, sl[x]<v を満たす最大のxを探す
// find x of sl[x] < v. return -1 if no lowerbound found
func lowerBound(v int, sl []int) int {
	if len(sl) == 0 {
		panic("slise len is zero")
	}
	idx := bs(0, len(sl)-1, func(c int) bool {
		return sl[c] < v
	})
	return idx
}

// ==================================================
// graph
// ==================================================

type edge struct {
	from int
	to   int
	cost int
	rev  int // 逆辺。最大フロー問題で使用
}

type state struct {
	node  int
	score int
}

/* n頂点を持つedgesグラフで頂点startからの距離をリストで返す。O((n+m)log n) */
func dijkstra(edges [][]edge, n, start int) []int {

	// g.starts = []state{{node: start}}

	score := make([]int, n)
	for i := 0; i < n; i++ {
		score[i] = inf
	}
	score[start] = 0

	que := newpq([]compFunc{
		func(p, q interface{}) int {
			if p.(state).score < q.(state).score {
				return -1
			} else if p.(state).score > q.(state).score {
				return 1
			} else {
				return 0
			}
		},
	})
	heap.Push(que, state{node: start, score: 0})

	for !que.IsEmpty() {
		st := heap.Pop(que).(state)
		if st.score > score[st.node] {
			continue
		}
		for _, edge := range edges[st.node] {
			newScore := st.score + edge.cost
			if score[edge.to] > newScore {
				score[edge.to] = newScore
				heap.Push(que, state{score: newScore, node: edge.to})
			}
		}
	}
	return score
}

/*
h := &OrgIntHeap{a, b, c}
heap.Init(h) 	// 使用する際にはまずInitを呼ぶ
heap.Push(h, v) // heap.Push経由で値を投入

	for !h.IsEmpty() {
		v = heap.Pop(h).(int) // heap.Pop経由で値を取り出す
	}
*/
type OrgIntHeap []int

func (h OrgIntHeap) Len() int { return len(h) }

// get from bigger
// func (h OrgIntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h OrgIntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h OrgIntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *OrgIntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *OrgIntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *OrgIntHeap) IsEmpty() bool {
	return h.Len() == 0
}

// h.Min().(int)
func (h *OrgIntHeap) Min() interface{} {
	return (*h)[0]
}

/*
	// 使い方の例
	// pqに入れるアイテムの型を定義
	type pqst struct {
		x int
		y int
	}

	pq := newpq([]compFunc{func(p, q interface{}) int {
		if p.(pqst).x != q.(pqst).x {
			// get from bigger
			// if p.(pqst).x > q.(pqst).x {
			if p.(pqst).x < q.(pqst).x {
				return -1
			} else {
				return 1
			}
		}
		if p.(pqst).y != q.(pqst).y {
			// get from bigger
			// if p.(pqst).y > q.(pqst).y {
			if p.(pqst).y < q.(pqst).y {
				return -1
			} else {
				return 1
			}
		}
		return 0
	}})

heap.Init(pq)
heap.Push(pq, pqst{x: 1, y: 1})

	for !pq.IsEmpty() {
		v := heap.Pop(pq).(pqst)
	}
*/
type pq struct {
	arr   []interface{}
	comps []compFunc
}

type compFunc func(p, q interface{}) int

func newpq(comps []compFunc) *pq {
	return &pq{
		comps: comps,
	}
}

func (pq pq) Len() int {
	return len(pq.arr)
}

func (pq pq) Swap(i, j int) {
	pq.arr[i], pq.arr[j] = pq.arr[j], pq.arr[i]
}

func (pq pq) Less(i, j int) bool {
	for _, comp := range pq.comps {
		result := comp(pq.arr[i], pq.arr[j])
		switch result {
		case -1:
			return true
		case 1:
			return false
		case 0:
			continue
		}
	}
	return true
}

func (pq *pq) Push(x interface{}) {
	pq.arr = append(pq.arr, x)
}

func (pq *pq) Pop() interface{} {
	n := pq.Len()
	item := pq.arr[n-1]
	pq.arr = pq.arr[:n-1]
	return item
}

func (pq *pq) IsEmpty() bool {
	return pq.Len() == 0
}

// pq.GetRoot().(edge)
func (pq *pq) GetRoot() interface{} {
	return pq.arr[0]
}

// ==================================================
// SCC (強連結成分分析)
// ==================================================
// step1 DFSで深い順にorderに追加
// step2 枝の方向を逆転し、orderの逆順にDFS
//
// 使い方
// n: 頂点数, edges: edgeの集合, r_edges: 反転したedgeの集合
// returns: 強連結成分ごとの頂点集合
func scc(n int, edges, r_edges [][]edge) [][]int {

	// step1
	order := []int{}
	used := make([]bool, n)

	var dfs func(v int)
	dfs = func(v int) {
		used[v] = true
		for _, next := range edges[v] {
			if !used[next.to] {
				dfs(next.to)
			}
		}
		order = append(order, v)
	}
	for v := 0; v < n; v++ {
		if !used[v] {
			dfs(v)
		}
	}

	// step2
	scc := [][]int{}
	used = make([]bool, n)

	var rdfs func(v, k int)
	rdfs = func(v, k int) {
		used[v] = true
		scc[k] = append(scc[k], v)
		for _, next := range r_edges[v] {
			if !used[next.to] {
				rdfs(next.to, k)
			}
		}
	}
	k := 0
	for i := n - 1; i >= 0; i-- {
		v := order[i]
		if !used[v] {
			scc = append(scc, []int{})
			rdfs(v, k)
			k++
		}
	}

	return scc
}

// ==================================================
// combination
// ==================================================
//
// 使い方
// c := newcombFactorial(n)
// nCr = c.comb(n,r)  *mod後のinteger

type combFactorial struct {
	fac    []int
	facinv []int
}

func newcombFactorial(n int) *combFactorial {

	fac := make([]int, n)
	facinv := make([]int, n)
	fac[0] = 1
	facinv[0] = minvfermat(1, mod)

	for i := 1; i < n; i++ {
		fac[i] = mmul(i, fac[i-1])
		facinv[i] = minvfermat(fac[i], mod)
	}

	return &combFactorial{
		fac:    fac,
		facinv: facinv,
	}
}

func (c *combFactorial) factorial(n int) int {
	return c.fac[n]
}

func (c *combFactorial) comb(n, r int) int {
	if r > n {
		return 0
	}
	return mmul(mmul(c.fac[n], c.facinv[r]), c.facinv[n-r])
}

func (c *combFactorial) permutation(n, r int) int {
	if r > n {
		return 0
	}
	return mmul(c.fac[n], c.facinv[n-r])
}

func (c *combFactorial) homogeousProduct(n, r int) int {
	return c.comb(n-1+r, r)
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

/*
	for {
		// Do something
		if !nextPermutation(sort.IntSlice(x)) {
			break
		}
	}
*/
func nextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

// ==================================================
// bit (Binary Index Tree)
// ==================================================
// newbit で長さn の配列用 treeを作成
// add(i, x) で 配列のi 番目の値をx加算
// sum(i) で配列の0-i番目までの値の累積和を計算

type bit struct {
	n int
	b []int
}

func newbit(n int) *bit {
	return &bit{
		n: n + 1,
		b: make([]int, n+1),
	}
}

func (b *bit) culc(i, j int) int {
	return i + j
	//return madd(i, j)
}

func (b *bit) add(i, x int) {
	for i++; i < b.n && i > 0; i += i & -i {
		b.b[i] = b.culc(b.b[i], x)
	}
}

func (b *bit) sum(i int) int {
	ret := 0
	for i++; i > 0; i -= i & -i {
		ret = b.culc(ret, b.b[i])
	}
	return ret
}

// ==================================================
// セグメント木（segment tree）
// ==================================================
// newstree(n,stmin|stmax|stadd|stmadd) でセグメント木を作成
// s.set(i,x)
// s.add(i,x)
// result1 := s.query(l,r)  // [l,r) の区間の値を返すことに注意

type streeculctype int

const (
	stadd streeculctype = iota
	stmadd
	stset
	stmin
	stmax
)

const inf = 1<<62 - 1

type stree struct {
	n   int
	b   []int
	def int
	cmp func(i, j int) int
}

func newstree(n int, minmax streeculctype) *stree {
	tn := 1
	for tn < n {
		tn *= 2
	}
	s := &stree{
		n: tn,
		b: make([]int, 2*tn-1),
	}
	switch minmax {
	case stmin:
		s.def = inf
		for i := 0; i < 2*tn-1; i++ {
			s.b[i] = s.def
		}
		s.cmp = func(i, j int) int {
			return min(i, j)
		}
	case stmax:
		s.cmp = func(i, j int) int {
			return max(i, j)
		}
	case stadd:
		s.cmp = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return i + j
		}
	case stmadd:
		s.cmp = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return madd(i, j)
		}
	}
	return s
}

func (s *stree) add(i, x int) {
	i += s.n - 1
	s.b[i] += x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

func (s *stree) set(i, x int) {
	i += s.n - 1
	s.b[i] = x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

func (s *stree) query(a, b int) int {
	return s.querysub(a, b, 0, 0, s.n)
}

func (s *stree) querysub(a, b, k, l, r int) int {
	if r <= a || b <= l {
		return s.def
	}
	if a <= l && r <= b {
		return s.b[k]
	}
	return s.cmp(
		s.querysub(a, b, k*2+1, l, (l+r)/2),
		s.querysub(a, b, k*2+2, (l+r)/2, r),
	)
}

// ==================================================
// 遅延評価セグメント木 (Lazy Segment Tree)
// ==================================================
// 区間の更新、加算を O(log n)でできるように改良したセグメント木
// s := newlazystree(n,stmin|stmax,stset|stadd|stmadd)　でインスタンス生成
// 2つ目の引数はqueryでの計算方法、3つ目の引数はupdateでの計算方法 (stsetは上書き、staddは加算、stmaddはmod加算)
//
// s.set(i,x),  s.add(i,x) は通常のセグメント木と同じ（遅延評価なし）
// s.update(l,r,x) で区間[l,r)をxで更新（遅延評価なのでこの時点ではセグメント木を更新しない）
// result1 := s.query(l,r) // [l,r) の区間の値を返すことに注意

type lazystree struct {
	on   int
	n    int
	b    []int
	lazy []int
	def  int
	cmp  func(i, j int) int
	culc func(i, j int) int
}

func newlazystree(n int, cmptype streeculctype, culctype streeculctype) lazystree {
	tn := 1
	for tn < n {
		tn *= 2
	}
	s := lazystree{
		on:   n,
		n:    tn,
		b:    make([]int, 2*tn-1),
		lazy: make([]int, 2*tn-1),
	}
	switch cmptype {
	case stmin:
		s.def = inf
		for i := 0; i < 2*tn-1; i++ {
			s.b[i] = s.def
			s.lazy[i] = s.def
		}
		s.cmp = func(i, j int) int {
			return min(i, j)
		}
	case stmax:
		s.cmp = func(i, j int) int {
			return max(i, j)
		}
	}
	switch culctype {
	case stadd:
		s.culc = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return i + j
		}
	case stmadd:
		s.culc = func(i, j int) int {
			if i == s.def {
				return j
			}
			if j == s.def {
				return i
			}
			return madd(i, j)
		}
	case stmax:
		s.culc = func(i, j int) int {
			return max(i, j)
		}
	case stmin:
		s.culc = func(i, j int) int {
			return min(i, j)
		}
	case stset:
		s.culc = func(i, j int) int {
			return j
		}
	}
	return s
}

func (s lazystree) eval(k int) {
	if s.lazy[k] == s.def {
		return
	}
	if k < s.n-1 {
		s.lazy[k*2+1] = s.culc(s.lazy[k*2+1], s.lazy[k])
		s.lazy[k*2+2] = s.culc(s.lazy[k*2+2], s.lazy[k])
	}
	s.b[k] = s.culc(s.b[k], s.lazy[k])
	s.lazy[k] = s.def
}

func (s lazystree) add(i, x int) {
	i += s.n - 1
	s.b[i] += x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

func (s lazystree) set(i, x int) {
	i += s.n - 1
	s.b[i] = x

	for i > 0 {
		i = (i - 1) / 2
		s.b[i] = s.cmp(s.b[i*2+1], s.b[i*2+2])
	}
}

// range culc a <= n n < b
func (s lazystree) update(a, b, x int) {
	s.rcsub(a, b, x, 0, 0, s.n)
}

func (s lazystree) rcsub(a, b, x, k, l, r int) {
	s.eval(k)
	if a <= l && r <= b {
		s.lazy[k] = s.culc(s.lazy[k], x)
		s.eval(k)
	} else if l < b && a < r {
		s.rcsub(a, b, x, k*2+1, l, (l+r)/2)
		s.rcsub(a, b, x, k*2+2, (l+r)/2, r)
		s.b[k] = s.cmp(s.b[k*2+1], s.b[k*2+2])
	}
}

func (s lazystree) get(a int) int {
	return s.query(a, a+1)
}

func (s lazystree) query(a, b int) int {
	return s.querysub(a, b, 0, 0, s.n)
}

func (s lazystree) querysub(a, b, k, l, r int) int {
	s.eval(k)
	if r <= a || b <= l {
		return s.def
	}
	if a <= l && r <= b {
		return s.b[k]
	}
	return s.cmp(
		s.querysub(a, b, k*2+1, l, (l+r)/2),
		s.querysub(a, b, k*2+2, (l+r)/2, r),
	)
}

/*
最大フロー問題を解く (Dinic法)
edges: Graph (逆辺を含む)
s: start
t: target
計算量はO(V^2 E)
*/
func maxflow(edges [][]edge, s, t int) int {
	n := len(edges)
	level := make([]int, n)
	iter := make([]int, n)
	flow := 0

	bfs := func(s int) {
		for i := 0; i < n; i++ {
			level[i] = -1
		}
		level[s] = 0
		q := list.New()
		q.PushBack(s)
		for q.Len() > 0 {
			v := q.Remove(q.Front()).(int)
			for i := 0; i < len(edges[v]); i++ {
				e := &edges[v][i]
				if e.cost > 0 && level[e.to] < 0 {
					level[e.to] = level[v] + 1
					q.PushBack(e.to)
				}
			}
		}
	}
	var dfs func(int, int, int) int
	dfs = func(v int, t int, f int) int {
		if v == t {
			return f
		}
		for i := iter[v]; i < len(edges[v]); i++ {
			iter[v] = i
			e := &edges[v][i]
			if e.cost > 0 && level[v] < level[e.to] {
				d := dfs(e.to, t, min(f, e.cost))
				if d > 0 {
					e.cost -= d
					edges[e.to][e.rev].cost += d
					return d
				}
			}
		}
		return 0
	}
	for {
		bfs(s)
		if level[t] < 0 {
			return flow
		}
		iter = make([]int, n)
		f := dfs(s, t, inf)
		for f > 0 {
			flow += f
			f = dfs(s, t, inf)
		}
	}
}

/*
	最大フロー問題の準備用

逆辺を追加する関数を作る
*/
func addEdge(edges [][]edge, from, to, cost int) {
	edges[from] = append(edges[from], edge{from, to, cost, len(edges[to])})
	edges[to] = append(edges[to], edge{to, from, 0, len(edges[from]) - 1})
}

/*
Zアルゴリズム: 文字列Sを与えてZ配列を返す。
Z[i]=S[0:]とS[i:]の先頭何文字が一致しているか？
*/
func z_algorithm(s string) []int {
	z := make([]int, len(s))
	z[0] = len(s)

	i, j := 1, 0
	for i < len(s) {
		for i+j < len(s) && s[j] == s[i+j] {
			j++
		}
		z[i] = j

		if j == 0 {
			i++
			continue
		}

		k := 1
		for k < j && k+z[k] < j {
			z[i+k] = z[k]
			k++
		}
		i += k
		j -= k
	}
	return z
}

func revstr(s string) string {
	r := []rune(s)
	for i := 0; i < len(r)/2; i++ {
		r[i], r[len(r)-i-1] = r[len(r)-i-1], r[i]
	}
	return string(r)
}

// ==================================================
// fft: 高速フーリエ変換
// ==================================================

/*
Convolution: 畳み込み
a, b: 畳み込む配列
C[i] = Σa[j]b[i-j] を O(NlogN) で求める (N=len(a)+len(b))
*/
func convolution(a, b []int) []int {
	n1, n2 := len(a), len(b)
	n := n1 + n2 - 1
	if n1 == 0 || n2 == 0 {
		return []int{}
	}

	z := 1 << ceilPow2(n)
	aa, bb := make([]int, z), make([]int, z)
	copy(aa, a)
	copy(bb, b)
	a, b = aa, bb

	butterfly(a, mod)
	butterfly(b, mod)
	for i := 0; i < z; i++ {
		a[i] = a[i] * b[i] % mod
	}
	butterflyInv(a, mod)
	a = a[:n]
	iz := minv(z, mod)
	for i := 0; i < n; i++ {
		a[i] = a[i] * iz % mod
		if a[i] < 0 {
			a[i] += mod
		}
	}

	return a
}

func primitiveRoot(m int) int {
	if m == 2 {
		return 1
	}
	if m == 167772161 || m == 469762049 || m == 998244353 {
		return 3
	}
	if m == 754974721 {
		return 11
	}
	divs := make([]int, 20)
	divs[0] = 2
	cnt := 1
	x := (m - 1) / 2
	for x%2 == 0 {
		x /= 2
	}
	for i := 3; i*i <= x; i += 2 {
		if x%i == 0 {
			divs[cnt] = i
			cnt++
			for x%i == 0 {
				x /= i
			}
		}
	}
	if x > 1 {
		divs[cnt] = x
		cnt++
	}
	for g := 2; ; g++ {
		ok := true
		for i := 0; i < cnt; i++ {
			if mpow(g, (m-1)/divs[i], m) == 1 {
				ok = false
				break
			}
		}
		if ok {
			return g
		}
	}
}

func ceilPow2(n int) int {
	x := 0
	for 1<<x < n {
		x++
	}
	return x
}

func bsf(n int) int {
	x := 0
	for n&(1<<x) == 0 {
		x++
	}
	return x
}

func butterfly(a []int, M int) {
	g := primitiveRoot(M)
	n := len(a)
	h := ceilPow2(n)

	se := make([]int, 30)
	es, ies := make([]int, 30), make([]int, 30)
	cnt2 := bsf(M - 1)
	e := mpow(g, (M-1)>>cnt2, M)
	ie := minv(e, M)
	for i := cnt2; i >= 2; i-- {
		es[i-2] = e
		ies[i-2] = ie
		e = e * e % M
		ie = ie * ie % M
	}
	now := 1
	for i := 0; i <= cnt2-2; i++ {
		se[i] = es[i] * now % M
		now = now * ies[i] % M
	}
	for ph := 1; ph <= h; ph++ {
		w := 1 << (ph - 1)
		p := 1 << (h - ph)
		now := 1
		for s := 0; s < w; s++ {
			offset := s << (h - ph + 1)
			for i := 0; i < p; i++ {
				l := a[i+offset]
				r := a[i+offset+p] * now % M
				a[i+offset] = (l + r) % M
				a[i+offset+p] = (M + l - r) % M
			}
			now = now * se[bsf(^s)] % M
		}
	}
}

func butterflyInv(a []int, M int) {
	g := primitiveRoot(M)
	n := len(a)
	h := ceilPow2(n)

	sie := make([]int, 30)
	es, ies := make([]int, 30), make([]int, 30)
	cnt2 := bsf(M - 1)
	e := mpow(g, (M-1)>>cnt2, M)
	ie := minv(e, M)
	for i := cnt2; i >= 2; i-- {
		es[i-2] = e
		ies[i-2] = ie
		e = e * e % M
		ie = ie * ie % M
	}
	now := 1
	for i := 0; i <= cnt2-2; i++ {
		sie[i] = ies[i] * now % M
		now = now * es[i] % M
	}
	for ph := h; ph >= 1; ph-- {
		w := 1 << (ph - 1)
		p := 1 << (h - ph)
		inow := 1
		for s := 0; s < w; s++ {
			offset := s << (h - ph + 1)
			for i := 0; i < p; i++ {
				l := a[i+offset]
				r := a[i+offset+p]
				a[i+offset] = (l + r) % M
				a[i+offset+p] = (M + l - r) * inow % M
			}
			inow = inow * sie[bsf(^s)] % M
		}
	}
}

Java solution:
import java.util.*;
import java.util.function.*;
import java.util.stream.*;
import java.io.*;

class Solve extends Util {
  void solve() {
    int n = in.i();
    long[] a = in.la(n);
    int[] p = in.ia(n - 1, 1);

    int[] d = new int[n];
    for (int i = 1; i < n; i++) d[i] = d[p[i] - 1] + 1;

    long[] sum = new long[n];
    for (int i = 0; i < n; i++) sum[d[i]] += a[i];

    //out.aas(d); out.aas(sum);

    for (int i = n - 1; i >= 0; i--) {
      if (sum[i] == 0) continue;
      out.an(sum[i] > 0 ? '+' : '-');
      return;
    }
    out.an(0);
  }
}























// My Library
// Version: 2023.10.21
// =================================================================================================

// TODO:
// * end を半開区間にする

public class Main extends Util {
  public static void main(String[] args) {
    try {
      new Solve().solve();
    } catch (Exception e) {
      throw e;
    } finally {
      out.flush();
    }
  }
}

@FunctionalInterface
interface F1<T, R> extends Function<T, R> {
  default R x(T t) { return apply(t); }
}
@FunctionalInterface
interface F2<T, U, R> extends BiFunction<T, U, R> {
  default F1<U, R> x(T p1) { return p2 -> apply(p1, p2); }
  default F1<T, F1<U, R>> currying() { return p1 -> p2 -> apply(p1, p2); }
  default F2<U, T, R> flip() { return (p1, p2) -> apply(p2, p1); }
}
@FunctionalInterface
interface F3<T, U, V, R> {
  R apply(T t, U u, V v);
  default F2<U, V, R> x(T p1) { return (p2, p3) -> apply(p1, p2, p3); }
  default F1<V, R> x(T p1, U p2) { return p3 -> apply(p1, p2, p3); }
  default F1<T, F1<U, F1<V, R>>> currying() { return p1 -> p2 -> p3 -> apply(p1, p2, p3); }
  default F3<V, U, T, R> flip() { return (p1, p2, p3) -> apply(p3, p2, p1); }
}
@FunctionalInterface
interface F4<T, U, V, W, R> {
  R apply(T t, U u, V v, W w);
  default F3<U, V, W, R> x(T p1) { return (p2, p3, p4) -> apply(p1, p2, p3, p4); }
  default F2<V, W, R> x(T p1, U p2) { return (p3, p4) -> apply(p1, p2, p3, p4); }
  default F1<W, R> x(T p1, U p2, V p3) { return p4 -> apply(p1, p2, p3, p4); }
  default F1<T, F1<U, F1<V, F1<W, R>>>> currying() { return p1 -> p2 -> p3 -> p4 -> apply(p1, p2, p3, p4); }
  default F4<W, V, U, T, R> flip() { return (p1, p2, p3, p4) -> apply(p4, p3, p2, p1); }
}
@FunctionalInterface
interface F5<T, U, V, W, X, R> {
  R apply(T t, U u, V v, W w, X x);
  default F4<U, V, W, X, R> x(T p1) { return (p2, p3, p4, p5) -> apply(p1, p2, p3, p4, p5); }
  default F3<V, W, X, R> x(T p1, U p2) { return (p3, p4, p5) -> apply(p1, p2, p3, p4, p5); }
  default F2<W, X, R> x(T p1, U p2, V p3) { return (p4, p5) -> apply(p1, p2, p3, p4, p5); }
  default F1<X, R> x(T p1, U p2, V p3, W p4) { return p5 -> apply(p1, p2, p3, p4, p5); }
  default F1<T, F1<U, F1<V, F1<W, F1<X, R>>>>> currying() { return p1 -> p2 -> p3 -> p4 -> p5 -> apply(p1, p2, p3, p4, p5); }
  default F5<X, W, V, U, T, R> flip() { return (p1, p2, p3, p4, p5) -> apply(p5, p4, p3, p2, p1); }
}
@FunctionalInterface
interface F6<T, U, V, W, X, Y, R> {
  R apply(T t, U u, V v, W w, X x, Y y);
  default F5<U, V, W, X, Y, R> x(T p1) { return (p2, p3, p4, p5, p6) -> apply(p1, p2, p3, p4, p5, p6); }
  default F4<V, W, X, Y, R> x(T p1, U p2) { return (p3, p4, p5, p6) -> apply(p1, p2, p3, p4, p5, p6); }
  default F3<W, X, Y, R> x(T p1, U p2, V p3) { return (p4, p5, p6) -> apply(p1, p2, p3, p4, p5, p6); }
  default F2<X, Y, R> x(T p1, U p2, V p3, W p4) { return (p5, p6) -> apply(p1, p2, p3, p4, p5, p6); }
  default F1<Y, R> x(T p1, U p2, V p3, W p4, X p5) { return p6 -> apply(p1, p2, p3, p4, p5, p6); }
  default F1<T, F1<U, F1<V, F1<W, F1<X, F1<Y, R>>>>>> currying() { return p1 -> p2 -> p3 -> p4 -> p5 -> p6 -> apply(p1, p2, p3, p4, p5, p6); }
  default F6<Y, X, W, V, U, T, R> flip() { return (p1, p2, p3, p4, p5, p6) -> apply(p6, p5, p4, p3, p2, p1); }
}
@FunctionalInterface
interface F7<T, U, V, W, X, Y, Z, R> {
  R apply(T t, U u, V v, W w, X x, Y y, Z z);
  default F6<U, V, W, X, Y, Z, R> x(T p1) { return (p2, p3, p4, p5, p6, p7) -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F5<V, W, X, Y, Z, R> x(T p1, U p2) { return (p3, p4, p5, p6, p7) -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F4<W, X, Y, Z, R> x(T p1, U p2, V p3) { return (p4, p5, p6, p7) -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F3<X, Y, Z, R> x(T p1, U p2, V p3, W p4) { return (p5, p6, p7) -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F2<Y, Z, R> x(T p1, U p2, V p3, W p4, X p5) { return (p6, p7) -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F1<Z, R> x(T p1, U p2, V p3, W p4, X p5, Y p6) { return p7 -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F1<T, F1<U, F1<V, F1<W, F1<X, F1<Y, F1<Z, R>>>>>>> currying() { return p1 -> p2 -> p3 -> p4 -> p5 -> p6 -> p7 -> apply(p1, p2, p3, p4, p5, p6, p7); }
  default F7<Z, Y, X, W, V, U, T, R> flip() { return (p1, p2, p3, p4, p5, p6, p7) -> apply(p7, p6, p5, p4, p3, p2, p1); }
}

class RLENode<T> {
  T val;
  int len;
  RLENode(T val, int len) {
    this.val = val;
    this.len = len;
  }
}
// FIXME:
class RLE<T> {
  RLENode<T>[] values;

  public RLE(T[] target) {
    if (target.length == 0) {
      @SuppressWarnings("unchecked")
      RLENode<T>[] array = new RLENode[0];
      values = array;
      return;
    }

    List<RLENode<T>> list = new ArrayList<>();
    T cur = target[0];
    int cnt = 1;
    for (int i = 1; i < target.length; i++) {
      if (target[i].equals(cur)) { // NOTE: 参照比較をしないように注意
        cnt++;
      } else {
        list.add(new RLENode<T>(cur, cnt));
        cur = target[i];
        cnt = 1;
      }
    }
    list.add(new RLENode<T>(cur, cnt));
    @SuppressWarnings("unchecked")
    RLENode<T>[] array = list.toArray(RLENode[]::new);
    values = array;
  }

  void print() {
    for (int i = 0; i < values.length; i++) {
      System.out.println(values[i].val + " " + values[i].len);
    }
  }

  HashMap<T, Integer> toMap() {
    HashMap<T, Integer> map = new HashMap<>();
    for (int i = 0; i < values.length; i++) {
      map.put(values[i].val, values[i].len);
    }
    return map;
  }
}

class Graph {
  List<Integer>[] edges;
  int[] weights;
  int n;
  boolean sortedEdges;
  boolean isDirected;

  @SuppressWarnings("unchecked")
  Graph(int n, boolean isDirected, boolean sortEdges) {
    this.n = n;
    this.edges = new ArrayList[n+1];
    for (int i = 1; i <= n; i++) {
      edges[i] = new ArrayList<Integer>();
    }
    this.weights = new int[n+1];
    this.sortedEdges = !sortEdges;
    this.isDirected = isDirected;
  }

  Graph(int n, boolean isDirected) {
    this(n, isDirected, false);
  }

  public void addEdge(int u, int v) {
    assert 1 <= u && u <= n;
    assert 1 <= v && v <= n;
    edges[u].add(v);
    if (!isDirected) edges[v].add(u);
    sortedEdges = false;
  }

  public void addEdge(int[] u, int[] v) {
    assert u != null && v != null;
    assert u.length == v.length;
    for (int i = 0; i < u.length; i++) addEdge(u[i], v[i]);
  }

  private void sortEdges() {
    for (int i = 1; i <= n; i++) Collections.sort(this.edges[i]);
    sortedEdges = true;
  }

  public List<Integer> bfs(Graph g, int s) {
    int[] ps = new int[this.n+1];
    int[] ds = new int[this.n+1];
    int[] cs = new int[this.n+1];
    List<Integer> path = new ArrayList<Integer>();
    Arrays.fill(ds, Integer.MAX_VALUE);
    ds[s] = 0;

    Deque<Integer> q = new ArrayDeque<Integer>();
    q.add(s);
    cs[s] = 1;

    while (!q.isEmpty()) {
      int u = q.remove();
      path.add(u);
      for (int v : g.edges[u]) {
        if (cs[v] == 0) {
          ps[v] = u;
          ds[v] = ds[u] + 1;
          cs[v] = 1;
          q.add(v);
        }
      }
      cs[u] = 2;
    }

    return path;
  }

  public int[] dfs(int s, int g) {
    int[] ds = new int[n+1]; // depth
    int[] fs = new int[n+1]; // first discovered
    int[] cs = new int[n+1]; // color (0: white, 1: gray, 2: black)
    int[] pi = new int[n+1]; // parent index
    List<Integer> path = new ArrayList<Integer>();
    int time = 0;

    sortEdges();
    dfs(ds, fs, cs, pi, path, time, s, g);

    int[] res = Util.toIntArray(path);
    Util.reverse(res);

    return res;
  }

  public boolean dfs(int[] ds, int[] fs, int[] cs, int[] pi, List<Integer> path, int time, int u, int g) {
    time++;
    ds[u] = time;
    cs[u] = 1;
    if (u == g) {
      path.add(u);
      return true;
    }
    for (int v : this.edges[u]) {
      if (pi[u] != v) {
        pi[v] = u;
        boolean res = dfs(ds, fs, cs, pi, path, time, v, g);
        if (res) {
          path.add(u);
          return true;
        }
      }
    }
    cs[u] = 2;
    time++;
    fs[u] = time;
    return false;
  }
}

// convert list, array, map, set, queue, stack
class Test {
  public static long pow(long a, long b, long mod) {
    if (b == 0) return 1;
    if (b == 1) return a;
    if (b % 2 == 0) return pow(a * a % mod, b / 2, mod);
    return a * pow(a * a % mod, b / 2, mod) % mod;
  }

  public static void sortSome(long[] key, long[]... value) {
    long[][] array = new long[key.length][1+value.length];
    for (int i = 0; i < key.length; i++) {
      array[0][i] = key[i];
      for (int j = 1; j < array[i].length; j++) {
        array[j][i] = value[j-1][i];
      }
    }
    Arrays.sort(array, Comparator.comparingLong(a -> a[0]));
  }

  public static long[] primeFact(long n, boolean allow_dup) {
    List<Long> list = new ArrayList<>();
    int upper = (int)Math.sqrt(n) + 1;
    for (long i = 2; i <= upper; i++) {
      if (n % i != 0) continue;
      list.add(i);
      n /= i;
      while (n % i == 0) {
        if (allow_dup) list.add(i);
        n /= i;
      }
    }
    if (n != 1) list.add(n);
    return list.stream().mapToLong(i -> i).toArray();
  }
  static List<long[]> permutation(long[] seed) {
    List<long[]> list = new ArrayList<>();
    long[] perm = new long[seed.length];
    boolean[] used = new boolean[seed.length];
    buildPerm(list, seed, perm, used, 0);
    return list;
  }
  static void buildPerm(List<long[]> list, long[] seed, long[] perm, boolean[] used, int index) {
    if (index == seed.length) {
      list.add(perm.clone());
      return;
    }
    for (int i = 0; i < seed.length; i++) {
      if (used[i]) continue;
      perm[index] = seed[i];
      used[i] = true;
      buildPerm(list, seed, perm, used, index + 1);
      used[i] = false;
    }
  }

  static void combInternal(List<int[]> res, int input[], int empty[], int start, int end, int index, int r) {
    if (index == r) {
      res.add(Arrays.copyOf(empty, r));
      return;
    }

    for (int y = start; y <= end && end - y + 1 >= r - index; y++) {
      empty[index] = input[y];
      combInternal(res, input, empty, y + 1, end, index + 1, r);
    }
  }

  static List<int[]> combination(int input[], int n, int r) {
    int empty[] = new int[r];
    List<int[]> list = new ArrayList<>();
    combInternal(list, input, empty, 0, n-1, 0, r);
    return list;
  }

  // ダイクストラ法
  // スタート頂点から全ての頂点への最短距離を返す
  static long[] dijkstra(int n, List<Integer>[] edges, long[][] costs, int start) {
    assert n == edges.length && n == costs.length;
    long[] ans = new long[n];
    Arrays.fill(ans, Integer.MAX_VALUE);
    boolean[] used = new boolean[n];

    // スタート地点をセット
    ans[start] = 0;
    for (int next : edges[start]) ans[next] = costs[start][next];

    for (int a = 0; a < n - 1; a++) {
      // 最小コストの頂点を見つける
      int minIndex = -1;
      long minValue = Long.MAX_VALUE;
      for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        if (ans[i] < minValue) {
          minIndex = i;
          minValue = ans[i];
        }
      }
      // 最小コストの頂点を選択する
      used[minIndex] = true;
      for (int next : edges[minIndex]) {
        long nextCost = ans[minIndex] + costs[minIndex][next];
        if (ans[next] > nextCost) {
          assert !used[next];
          ans[next] = nextCost;
        }
      }
    }

    return ans;
  }
}

class Util {
  static In in = new In();
  static Out out = new Out();
  public static final int N10_9 = 1000000000;
  public static final int N10_9_7 = 1000000007;
  public static final char[] abc = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
                                    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
  public static final char[] ABC = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
                                    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

  public static void sort(Object[] a) {
    Arrays.sort(a);
  }
  public static <T> void sort(T[] a, Comparator<? super T> c) {
    Arrays.sort(a, c);
  }
  public static void sort(int[] a) {
    Arrays.sort(a);
  }
  public static void sort(int[] a, int from, int to) {
    Arrays.sort(a, from, to);
  }
  public static void sort(long[] a) {
    Arrays.sort(a);
  }
  public static void sort(long[] a, int from, int to) {
    Arrays.sort(a, from, to);
  }
  public static void sort(double[] a) {
    Arrays.sort(a);
  }
  public static void sort(double[] a, int from, int to) {
    Arrays.sort(a, from, to);
  }
  public static void sort(char[] a) {
    Arrays.sort(a);
  }
  public static void sort(char[] a, int from, int to) {
    Arrays.sort(a, from, to);
  }

  public static int gcd(int a, int b) {
    return MyMath.gcd(a, b);
  }
  public static long gcd(long a, long b) {
    return MyMath.gcd(a, b);
  }
  public static int lcm(int a, int b) {
      return MyMath.lcm(a, b);
  }
  public static long lcm(long a, long b) {
      return MyMath.lcm(a, b);
  }

  public static int sum(int[] a, int start, int end) {
    int sum = 0;
    for (int i = start; i < end; i++) sum += a[i];
    return sum;
  }
  public static long sum(long[] a, int start, int end) {
    long sum = 0;
    for (int i = start; i < end; i++) sum += a[i];
    return sum;
  }
  public static double sum(double[] a, int start, int end) {
    double sum = 0;
    for (int i = start; i < end; i++) sum += a[i];
    return sum;
  }
  public static int sum(int[] a) {
    return sum(a, 0, a.length);
  }
  public static long sum(long[] a) {
    return sum(a, 0, a.length);
  }
  public static double sum(double[] a) {
    return sum(a, 0, a.length);
  }
  public static int sum(int a, int ... b) {
    return a + sum(b);
  }
  public static long sum(long a, long ... b) {
    return a + sum(b);
  }
  public static double sum(double a, double ... b) {
    return a + sum(b);
  }

  public static int lower_bound(List<Integer> list, int target) {
    return ~Collections.binarySearch(list, target, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1);
  }

  public static int upper_bound(List<Integer> list, int target) {
    return ~Collections.binarySearch(list, target, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);
  }

  public static int lower_bound(List<Long> list, long target) {
    return ~Collections.binarySearch(list, target, (x, y) -> x.compareTo(y) >= 0 ? 1 : -1);
  }

  public static int upper_bound(List<Long> list, long target) {
    return ~Collections.binarySearch(list, target, (x, y) -> x.compareTo(y) > 0 ? 1 : -1);
  }

  // ビット全探索
  public static boolean[][] bitAll(int n) {
    boolean[][] res = new boolean[1 << n][n];
    for (int i = 0; i < 1 << n; i++) {
      for (int j = 0; j < n; j++) {
        res[i][j] = (i >> j & 1) == 1;
      }
    }
    return res;
  }
  public static boolean[][] bitAll(int n, int bitCount) {
    List<boolean[]> res = new ArrayList<>();
    boolean[] b = new boolean[n];
    for (int i = (1 << bitCount) - 1; i < 1 << n;) {
      assert Integer.bitCount(i) == bitCount;

      for (int j = 0; j < n; j++) b[j] = (i >> j & 1) == 1;
      res.add(b.clone());

      int t = i | i - 1;
      i = t + 1 | (~t & -~t) - 1 >> Integer.numberOfTrailingZeros(i) + 1;
    }
    return toBooleanArrayArray(res);
  }
  public static int[][] bitAllFilter(boolean[][] use, int[] array) {
    int[][] res = new int[use.length][];
    for (int i = 0; i < use.length; i++) {
      int size = 0;
      for (int j = 0; j < use[i].length; j++) if (use[i][j]) size++;
      res[i] = new int[size];
      int index = 0;
      for (int j = 0; j < array.length; j++)
        if (use[i][j]) res[i][index++] = array[j];
    }
    return res;
  }
  public static long[][] bitAllFilter(boolean[][] use, long[] array) {
    long[][] res = new long[use.length][];
    for (int i = 0; i < use.length; i++) {
      int size = 0;
      for (int j = 0; j < use[i].length; j++) if (use[i][j]) size++;
      res[i] = new long[size];
      int index = 0;
      for (int j = 0; j < array.length; j++)
        if (use[i][j]) res[i][index++] = array[j];
    }
    return res;
  }
  public static double[][] bitAllFilter(boolean[][] use, double[] array) {
    double[][] res = new double[use.length][];
    for (int i = 0; i < use.length; i++) {
      int size = 0;
      for (int j = 0; j < use[i].length; j++) if (use[i][j]) size++;
      res[i] = new double[size];
      int index = 0;
      for (int j = 0; j < array.length; j++)
        if (use[i][j]) res[i][index++] = array[j];
    }
    return res;
  }
  public static Object[][] bitAllFilter(boolean[][] use, Object[] array) {
    Object[][] res = new Object[use.length][];
    for (int i = 0; i < use.length; i++) {
      int size = 0;
      for (int j = 0; j < use[i].length; j++) if (use[i][j]) size++;
      res[i] = new Object[size];
      int index = 0;
      for (int j = 0; j < array.length; j++)
        if (use[i][j]) res[i][index++] = array[j];
    }
    return res;
  }
  public static int[][][] bitAllFilter(boolean[][] use, int[][] array) {
    int[][][] res = new int[use.length][][];
    for (int i = 0; i < use.length; i++) {
      int size = 0;
      for (int j = 0; j < use[i].length; j++) if (use[i][j]) size++;
      res[i] = new int[size][];
      int index = 0;
      for (int j = 0; j < array.length; j++)
        if (use[i][j]) res[i][index++] = array[j];
    }
    return res;
  }
  public static long[][][] bitAllFilter(boolean[][] use, long[][] array) {
    long[][][] res = new long[use.length][][];
    for (int i = 0; i < use.length; i++) {
      int size = 0;
      for (int j = 0; j < use[i].length; j++) if (use[i][j]) size++;
      res[i] = new long[size][];
      int index = 0;
      for (int j = 0; j < array.length; j++)
        if (use[i][j]) res[i][index++] = array[j];
    }
    return res;
  }

  public static int[] arrayRange(int start, int end, int headspace, int tailspace) {
    int n = end - start + 1;
    int[] res = new int[n + headspace + tailspace];
    int cur = start;
    for (int i = headspace; i < n + headspace; i++) res[i] = cur++;
    return res;
  }
  public static int[] arrayRange(int start, int end) {
    return arrayRange(start, end, 0, 0);
  }

  public static long[] arrayRange(long start, long end, int headspace, int tailspace) {
    long n = end - start + 1;
    long[] res = new long[(int)n + headspace + tailspace];
    long cur = start;
    for (int i = headspace; i < n + headspace; i++) res[i] = cur++;
    return res;
  }
  public static long[] arrayRange(long start, long end) {
    return arrayRange(start, end, 0, 0);
  }

  public static long[] toLongArray(Collection<?> list) {
    return list.stream().mapToLong(i -> (long)i).toArray();
  }
  public static int[] toIntArray(Collection<?> list) {
    return list.stream().mapToInt(i -> (int)i).toArray();
  }
  public static double[] toDoubleArray(Collection<?> list) {
    return list.stream().mapToDouble(i -> (double)i).toArray();
  }
  public static boolean[] toBooleanArray(Collection<?> list) {
    Object[] a = list.toArray();
    boolean[] b = new boolean[a.length];
    for (int i = 0; i < b.length; i++) {
      b[i] = (boolean)a[i];
    }
    return b;
  }
  public static String[] toStringArray(Collection<?> list) {
    return list.stream().map(i -> i.toString()).toArray(String[]::new);
  }

  public static long[][] toLongArrayArray(Collection<?> list) {
    return list.toArray(long[][]::new);
  }
  public static int[][] toIntArrayArray(Collection<?> list) {
    return list.toArray(int[][]::new);
  }
  public static double[][] toDoubleArrayArray(Collection<?> list) {
    return list.toArray(double[][]::new);
  }
  public static boolean[][] toBooleanArrayArray(Collection<?> list) {
    return list.toArray(boolean[][]::new);
  }
  public static String[][] toStringArrayArray(Collection<?> list) {
    return list.toArray(String[][]::new);
  }

  public static <T> void reverse(T[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(boolean[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(int[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(long[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(double[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(float[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(byte[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }
  public static void reverse(char[] array) {
    int len = array.length;
    for (int i = 0; i < len / 2; i++) swap(array, i, len - i - 1);
  }

  public static int[] distinct(int[] a) {
    return Arrays.stream(a).distinct().toArray();
  }
  public static long[] distinct(long[] a) {
    return Arrays.stream(a).distinct().toArray();
  }
  public static double[] distinct(double[] a) {
    return Arrays.stream(a).distinct().toArray();
  }

  public static void fill(int[] a, int v) {
    Arrays.fill(a, v);
  }
  public static void fill(long[] a, long v) {
    Arrays.fill(a, v);
  }
  public static void fill(double[] a, double v) {
    Arrays.fill(a, v);
  }
  public static void fill(boolean[] a, boolean v) {
    Arrays.fill(a, v);
  }
  public static void fill(char[] a, char v) {
    Arrays.fill(a, v);
  }

  public static void fill(int[][] a, int v) {
    for (int[] i : a) fill(i, v);
  }
  public static void fill(long[][] a, long v) {
    for (long[] i : a) fill(i, v);
  }
  public static void fill(double[][] a, double v) {
    for (double[] i : a) fill(i, v);
  }
  public static void fill(boolean[][] a, boolean v) {
    for (boolean[] i : a) fill(i, v);
  }
  public static void fill(char[][] a, char v) {
    for (char[] i : a) fill(i, v);
  }

  public static void fill(int[][][] a, int v) {
    for (int[][] i : a) fill(i, v);
  }
  public static void fill(long[][][] a, long v) {
    for (long[][] i : a) fill(i, v);
  }
  public static void fill(double[][][] a, double v) {
    for (double[][] i : a) fill(i, v);
  }
  public static void fill(boolean[][][] a, boolean v) {
    for (boolean[][] i : a) fill(i, v);
  }
  public static void fill(char[][][] a, char v) {
    for (char[][] i : a) fill(i, v);
  }

  public static void fill(int[][][][] a, int v) {
    for (int[][][] i : a) fill(i, v);
  }
  public static void fill(long[][][][] a, long v) {
    for (long[][][] i : a) fill(i, v);
  }
  public static void fill(double[][][][] a, double v) {
    for (double[][][] i : a) fill(i, v);
  }
  public static void fill(boolean[][][][] a, boolean v) {
    for (boolean[][][] i : a) fill(i, v);
  }
  public static void fill(char[][][][] a, char v) {
    for (char[][][] i : a) fill(i, v);
  }

  // NOTE: These methods require Java 16 or higher.
  public static List<Long> arrayToList(long[] array) {
    return Arrays.stream(array).boxed().collect(Collectors.toList());
    //return Arrays.stream(array).boxed().toList();
  }
  public static List<Integer> arrayToList(int[] array) {
    return Arrays.stream(array).boxed().collect(Collectors.toList());
    //return Arrays.stream(array).boxed().toList();
  }
  public static List<Double> arrayToList(double[] array) {
    return Arrays.stream(array).boxed().collect(Collectors.toList());
    //return Arrays.stream(array).boxed().toList();
  }
  public static List<Boolean> arrayToList(boolean[] array) {
    Boolean[] a = new Boolean[array.length];
    for (int i = 0; i < a.length; i++) a[i] = array[i];
    return Arrays.stream(a).collect(Collectors.toList());
    //return Arrays.stream(a).toList();
  }
  public static List<Character> arrayToList(char[] array) {
    return Arrays.stream(arrayBoxed(array)).collect(Collectors.toList());
  }
  public static <T> List<T> arrayToList(T[] array) {
    return Arrays.stream(array).collect(Collectors.toList());
    //return Arrays.stream(array).toList();
  }

  public static Long[] arrayBoxed(long[] array) {
    return Arrays.stream(array).boxed().toArray(Long[]::new);
  }
  public static Integer[] arrayBoxed(int[] array) {
    return Arrays.stream(array).boxed().toArray(Integer[]::new);
  }
  public static Double[] arrayBoxed(double[] array) {
    return Arrays.stream(array).boxed().toArray(Double[]::new);
  }
  public static Boolean[] arrayBoxed(boolean[] array) {
    Boolean[] a = new Boolean[array.length];
    for (int i = 0; i < array.length; i++) {
      a[i] = array[i];
    }
    return a;
  }
  public static Character[] arrayBoxed(char[] array) {
    Character[] a = new Character[array.length];
    for (int i = 0; i < array.length; i++) {
      a[i] = array[i];
    }
    return a;
  }

  public static long[] arrayUnboxed(Long[] array) {
    return Arrays.stream(array).mapToLong(i -> i).toArray();
  }
  public static int[] arrayUnboxed(Integer[] array) {
    return Arrays.stream(array).mapToInt(i -> i).toArray();
  }
  public static double[] arrayUnboxed(Double[] array) {
    return Arrays.stream(array).mapToDouble(i -> i).toArray();
  }
  public static boolean[] arrayUnboxed(Boolean[] array) {
    boolean[] a = new boolean[array.length];
    for (int i = 0; i < array.length; i++) {
      a[i] = array[i];
    }
    return a;
  }
  public static char[] arrayUnboxed(Character[] array) {
    char[] a = new char[array.length];
    for (int i = 0; i < array.length; i++) {
      a[i] = array[i];
    }
    return a;
  }

  // 最大値 (int)
  public static int max(int a, int b) {
    return Math.max(a, b);
  }
  public static int max(int a, int ... nums) {
    return max(a, max(nums));
  }
  public static int max(int[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = a[0];
    for (int i = start; i <= end; i++) res = Math.max(res, a[i]);
    return res;
  }
  public static int max(int[] a, int start) {
    return max(a, start, a.length - 1);
  }
  public static int max(int[] a) {
    return max(a, 0, a.length - 1);
  }
  public static int maxIndex(int[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = start;
    for (int i = start; i <= end; i++) {
      if (a[i] > a[res]) res = i;
    }
    return res;
  }
  public static int maxIndex(int[] a, int start) {
    return maxIndex(a, start, a.length - 1);
  }
  public static int maxIndex(int[] a) {
    return maxIndex(a, 0, a.length - 1);
  }

  // 最小値 (int)
  public static int min(int a, int b) {
    return Math.min(a, b);
  }
  public static int min(int a, int ... nums) {
    return min(a, min(nums));
  }
  public static int min(int[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = a[0];
    for (int i = start; i <= end; i++) res = Math.min(res, a[i]);
    return res;
  }
  public static int min(int[] a, int start) {
    return min(a, start, a.length - 1);
  }
  public static int min(int[] a) {
    return min(a, 0, a.length - 1);
  }
  public static int minIndex(int[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = start;
    for (int i = start; i <= end; i++) {
      if (a[i] < a[res]) res = i;
    }
    return res;
  }
  public static int minIndex(int[] a, int start) {
    return minIndex(a, start, a.length - 1);
  }
  public static int minIndex(int[] a) {
    return minIndex(a, 0, a.length - 1);
  }

  // 最大値 (long)
  public static long max(long a, long b) {
    return Math.max(a, b);
  }
  public static long max(long a, long ... nums) {
    return max(a, max(nums));
  }
  public static long max(long[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    long res = a[0];
    for (int i = start; i <= end; i++) res = Math.max(res, a[i]);
    return res;
  }
  public static long max(long[] a, int start) {
    return max(a, start, a.length - 1);
  }
  public static long max(long[] a) {
    return max(a, 0, a.length - 1);
  }
  public static int maxIndex(long[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = start;
    for (int i = start; i <= end; i++) {
      if (a[i] > a[res]) res = i;
    }
    return res;
  }
  public static int maxIndex(long[] a, int start) {
    return maxIndex(a, start, a.length - 1);
  }
  public static int maxIndex(long[] a) {
    return maxIndex(a, 0, a.length - 1);
  }

  // 最小値 (long)
  public static long min(long a, long b) {
    return Math.min(a, b);
  }
  public static long min(long a, long ... nums) {
    return min(a, min(nums));
  }
  public static long min(long[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    long res = a[0];
    for (int i = start; i <= end; i++) res = Math.min(res, a[i]);
    return res;
  }
  public static long min(long[] a, int start) {
    return min(a, start, a.length - 1);
  }
  public static long min(long[] a) {
    return min(a, 0, a.length - 1);
  }
  public static int minIndex(long[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = start;
    for (int i = start; i <= end; i++) {
      if (a[i] < a[res]) res = i;
    }
    return res;
  }
  public static int minIndex(long[] a, int start) {
    return minIndex(a, start, a.length - 1);
  }
  public static int minIndex(long[] a) {
    return minIndex(a, 0, a.length - 1);
  }

  // 最大値 (double)
  public static double max(double a, double b) {
    return Math.max(a, b);
  }
  public static double max(double a, double ... nums) {
    return max(a, max(nums));
  }
  public static double max(double[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    double res = a[0];
    for (int i = start; i <= end; i++) res = Math.max(res, a[i]);
    return res;
  }
  public static double max(double[] a, int start) {
    return max(a, start, a.length - 1);
  }
  public static double max(double[] a) {
    return max(a, 0, a.length - 1);
  }
  public static int maxIndex(double[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = start;
    for (int i = start; i <= end; i++) {
      if (a[i] > a[res]) res = i;
    }
    return res;
  }
  public static int maxIndex(double[] a, int start) {
    return maxIndex(a, start, a.length - 1);
  }
  public static int maxIndex(double[] a) {
    return maxIndex(a, 0, a.length - 1);
  }

  // 最小値 (double)
  public static double min(double a, double b) {
    return Math.min(a, b);
  }
  public static double min(double a, double ... nums) {
    return min(a, min(nums));
  }
  public static double min(double[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    double res = a[0];
    for (int i = start; i <= end; i++) res = Math.min(res, a[i]);
    return res;
  }
  public static double min(double[] a, int start) {
    return min(a, start, a.length - 1);
  }
  public static double min(double[] a) {
    return min(a, 0, a.length - 1);
  }
  public static int minIndex(double[] a, int start, int end) {
    assert start >= 0 && end < a.length && start <= end;
    int res = start;
    for (int i = start; i <= end; i++) {
      if (a[i] < a[res]) res = i;
    }
    return res;
  }
  public static int minIndex(double[] a, int start) {
    return minIndex(a, start, a.length - 1);
  }
  public static int minIndex(double[] a) {
    return minIndex(a, 0, a.length - 1);
  }

  // 絶対値
  public static int abs(int a) {
    return Math.abs(a);
  }
  public static long abs(long a) {
    return Math.abs(a);
  }
  public static double abs(double a) {
    return Math.abs(a);
  }

  // チェビシェフ距離（チェス盤距離）
  public static long chebyshevDistance(long x1, long y1, long x2, long y2) {
    return max(abs(x1 - x2), abs(y1 - y2));
  }
  public static int chebyshevDistance(int x1, int y1, int x2, int y2) {
    return max(abs(x1 - x2), abs(y1 - y2));
  }

  // マンハッタン距離
  public static long manhattanDistance(long x1, long y1, long x2, long y2) {
    return abs(x1 - x2) + abs(y1 - y2);
  }
  public static int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
  }

  // ユークリッド距離
  public static int euclideanDistance(int x1, int y1, int x2, int y2) {
    return (int) Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
  }
  public static long euclideanDistance(long x1, long y1, long x2, long y2) {
    return (long) Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
  }

  // 外積
  public static long cross(long ox, long oy, long ax, long ay, long bx, long by) {
    // 外積: |a||b|sinθ = axby - bxay
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy);
  }
  public static long cross(long ax, long xy, long bx, long by) {
    // 外積: |a||b|sinθ = axby - bxay
    return cross(0, 0, ax, xy, bx, by);
  }

  // 内積
  public static long dot(long ox, long oy, long ax, long ay, long bx, long by) {
    // 内積: |a||b|cosθ = axbx + ayby
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy);
  }
  public static long dot(long ax, long xy, long bx, long by) {
    // 内積: |a||b|cosθ = axbx + ayby
    return dot(0, 0, ax, xy, bx, by);
  }

  // swap
  public static String swap(String s, int i, int j) {
    char[] cs = s.toCharArray();
    char tmp = cs[i]; cs[i] = cs[j]; cs[j] = tmp;
    return String.valueOf(cs);
  }
  public static void swap(boolean[] a, int i, int j) {
    boolean tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static void swap(int[] a, int i, int j) {
    int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static void swap(long[] a, int i, int j) {
    long tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static void swap(double[] a, int i, int j) {
    double tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static void swap(float[] a, int i, int j) {
    float tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static void swap(byte[] a, int i, int j) {
    byte tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static void swap(char[] a, int i, int j) {
    char tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static <T> void swap(T[] a, int i, int j) {
    T tmp = a[i]; a[i] = a[j]; a[j] = tmp;
  }
  public static <T> void swap(List<T> a, int i, int j) {
    T tmp = a.get(i); a.set(i, a.get(j)); a.set(j, tmp);
  }

  // 間にあるかどうか
  public static boolean between(int a, int x, int b) {
    if (a > b) return between(b, x, a);
    return a <= x && x <= b;
  }
  public static boolean between(long a, long x, long b) {
    if (a > b) return between(b, x, a);
    return a <= x && x <= b;
  }
  public static boolean between(double a, double x, double b) {
    if (a > b) return between(b, x, a);
    return a <= x && x <= b;
  }
  public static boolean between(float a, float x, float b) {
    if (a > b) return between(b, x, a);
    return a <= x && x <= b;
  }
  public static boolean between(byte a, byte x, byte b) {
    if (a > b) return between(b, x, a);
    return a <= x && x <= b;
  }
  public static boolean between(char a, char x, char b) {
    if (a > b) return between(b, x, a);
    return a <= x && x <= b;
  }

  // modpow (a^b mod m) 繰り返し二乗法
  public static long modpow(long a, long b, long m) {
    long res = 1;
    while (b > 0) {
      if ((b & 1) == 1) res = res * a % m;
      a = a * a % m;
      b >>= 1;
    }
    return res;
  }

  public static long modadd(long a, long b, long m) {
    return (a + b) % m;
  }

  public static long modsub(long a, long b, long m) {
    return (a - b + m) % m;
  }

  public static long modmul(long a, long b, long m) {
    return (a * b) % m;
  }

  public static long moddiv(long a, long b, long m) {
    return (a * modpow(b, m - 2, m)) % m;
  }
}

class ModInt {
  private long mod;
  private long val;

  public ModInt(long val, long mod) {
    this.mod = mod;
    this.val = val % mod;
  }

  public long toLong() {
    return val;
  }

  public String toString() {
    return String.valueOf(val);
  }

  // modpow (a^b mod m) 繰り返し二乗法
  public long pow(long x) {
    long res = 1;
    while (x > 0) {
      if ((x & 1) == 1) res = res * val % mod;
      val = val * val % mod;
      x >>= 1;
    }
    return res;
  }

  public long pow(long x, long m) {
    long res = 1;
    while (x > 0) {
      if ((x & 1) == 1) res = res * val % m;
      val = val * val % m;
      x >>= 1;
    }
    return res;
  }

  public long add(long x) {
    val += x;
    val %= mod;
    return val;
  }

  public long sub(long x) {
    val -= x;
    val += mod;
    val %= mod;
    return val;
  }

  public long mul(long x) {
    val *= x;
    val %= mod;
    return val;
  }

  public long div(long x) {
    val *= pow(x, mod - 2);
    val %= mod;
    return val;
  }
}

class MyMath {
  // 最大公約数 (Greatest Common Divisor)
  public static long gcd(long a, long b) {
    if (a < b) {
      long tmp = a; a = b; b = tmp;
    }
    while (b != 0) {
      long tmp = a % b; a = b; b = tmp;
    }
    return a;
  }
  public static int gcd(int a, int b) {
    if (a < b) {
      int tmp = a; a = b; b = tmp;
    }
    while (b != 0) {
      int tmp = a % b; a = b; b = tmp;
    }
    return a;
  }

  // 最小公倍数 (Least Common Multiple)
  public static long lcm(long a, long b) {
    return a * b / gcd(a, b);
  }
  public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
  }

  // 素数列挙 (Prime enumeration)
  public static int[] primes(int max) {
    return primes_base((int)Math.sqrt(max) + 1);
  }
  public static int[] primes_base(int max) {
    boolean[] is_prime = new boolean[max];
    for (int i = 0; i < max; i++) {
      is_prime[i] = true;
    }
    for (int i = 2; i < max; i++) {
      if (is_prime[i]) {
        for (int j = i * 2; j < max; j += i) {
          is_prime[j] = false;
        }
      }
    }
    int cnt = 0;
    for (int i = 2; i < max; i++) {
      if (is_prime[i]) cnt++;
    }
    int[] primes = new int[cnt];
    int index = 0;
    for (int i = 2; i < max && index < cnt; i++) {
      if (is_prime[i]) primes[index++] = i;
    }
    return primes;
  }
  // TODO:
  public static int[] primes_base_bit(int max) {
    long[] is_prime = new long[max/64+1];
    for (int i = 0; i < max; i++) {
      is_prime[i/64] = is_prime[i/64] | (1 << (i%64)); // is_prime[i] = true
    }
    for (int i = 2; i < max; i++) {
      if ((is_prime[i/64] & (1 << (i%64))) != 0) { // is_prime[i]
        for (int j = i * 2; j < max; j += i) {
          is_prime[j/64] = is_prime[j/64] & (~(1 << (j%64))); // is_prime[j] = false
        }
      }
    }
    int cnt = 0;
    for (int i = 2; i < max; i++) {
      if ((is_prime[i/64] & (1 << (i%64))) != 0) cnt++;  // is_prime[i]
    }
    int[] primes = new int[cnt];
    int index = 0;
    for (int i = 2; i < max && index < cnt; i++) {
      if ((is_prime[i/64] & (1 << (i%64))) != 0) primes[index++] = i;  // is_prime[i]
    }
    return primes;
  }
}

class In {
  private final InputStream in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;

  public In(InputStream in) {
    this.in = in;
  }

  public In() {
    this.in = System.in;
  }

  private final boolean hasNextByte() {
    if (ptr < buflen) return true;
    ptr = 0;
    try {
      buflen = in.read(buffer);
    } catch (IOException e) {
      e.printStackTrace();
    }
    if (buflen <= 0) return false;
    return true;
  }

  private final int readByte() {
    return hasNextByte() ? buffer[ptr++] : -1;
  }

  private static final boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }

  public final boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
      ptr++;
    }
    return hasNextByte();
  }

  public final String s() {
    StringBuilder sb = new StringBuilder();
    int b = readByte();
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  public final void nextThrow(int n) {
    for (int i = 0; i < n; i++) this.s();
  }

  public final void nextThrow() {
    this.nextThrow(1);
  }

  public final long l() {
    long n = 0;
    boolean minus = false;
    int b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    assert '0' <= b && b <= '9' : "NumberFormatException";
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else {
        //assert b == ' ' || b == '\n' : "NumberFormatException";
        return minus ? -n : n;
      }
      b = readByte();
    }
  }
  public long[] la(int n, int headspace, int tailspace) {
    long[] result = new long[n + headspace + tailspace];
    for (int i = headspace; i < n + headspace; i++) result[i] = l();
    return result;
  }
  public long[] la(int n, int headspace) {
    return la(n, headspace, 0);
  }
  public long[] la(int n) {
    return la(n, 0, 0);
  }

  // TODO:
  public long[][] laa(int n, int m) {
    long[][] result = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) result[i][j] = l();
    }
    return result;
  }

  public final int i() {
    long nl = l();
    assert (Integer.MIN_VALUE <= nl || nl <= Integer.MAX_VALUE) : "NumberFormatException";
    return (int)nl;
  }
  public int[] ia(int n, int headspace, int tailspace) {
    int[] result = new int[n + headspace + tailspace];
    for (int i = headspace; i < n + headspace; i++) result[i] = i();
    return result;
  }
  public int[] ia(int n, int headspace) {
    return ia(n, headspace, 0);
  }
  public int[] ia(int n) {
    return ia(n, 0, 0);
  }

  // TODO:
  public int[][] iaa(int n, int m) {
    int[][] result = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) result[i][j] = i();
    }
    return result;
  }
  public int[][] ias(int ncol, int n) {
    int[][] result = new int[ncol][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < ncol; j++) result[j][i] = i();
    }
    return result;
  }

  public double d() {
    return Double.parseDouble(s());
  }

  public boolean[] b(char True) {
    String s = this.s();
    int n = s.length();
    boolean[] array = new boolean[n];
    for (int i = 0; i < n; i++)
      array[i] = s.charAt(i) == True;
    return array;
  }
}

class Out {
  PrintWriter out;

  Out() {
    this.out = new PrintWriter(System.out);
  }

  public final void as() {
    out.print(' ');
  }
  public final void an() {
    out.print('\n');
  }

  public final <T> void a(T n) {
    out.print(n);
  }
  public final <T> void as(T n) {
    out.print(n);
    out.print(' ');
  }
  public final <T> void an(T n) {
    out.println(n);
  }

  public final void yesno(boolean b) {
    out.println(b ? "Yes" : "No");
  }

  public final void aas(int[] n) {
    int nm = n.length-1;
    for (int i = 0; i < nm; i++) {
      out.print(n[i]);
      out.print(' ');
    }
    out.println(n[nm]);
  }
  public final void aan(int[] n) {
    int nm = n.length-1;
    for (int i = 0; i < nm; i++) {
      out.println(n[i]);
    }
    out.println(n[nm]);
  }
  public final void aas(int[][] n) {
    int nm = n.length;
    for (int i = 0; i < nm; i++) {
      aas(n[i]);
    }
  }

  public final void aas(long[] n) {
    int nm = n.length-1;
    for (int i = 0; i < nm; i++) {
      out.print(n[i]);
      out.print(' ');
    }
    out.println(n[nm]);
  }
  public final void aan(long[] n) {
    int nm = n.length-1;
    for (int i = 0; i < nm; i++) {
      out.println(n[i]);
    }
    out.println(n[nm]);
  }
  public final void aas(long[][] n) {
    int nm = n.length;
    for (int i = 0; i < nm; i++) {
      aas(n[i]);
    }
  }

  public final void flush() {
    out.flush();
  }
  public final void flushln() {
    out.print('\n');
    out.flush();
  }
}

// Edge
class E {
  int u;
  int v;
  int w;

  public E(int u, int v, int w) {
    this.u = u;
    this.v = v;
    this.w = w;
  }

  public E(int u, int v) {
    this(u, v, 0);
  }
}

// Union-Find
class UF {
  int[] parent;
  int[] rank;
  int[] size;

  public UF(int n) {
    parent = new int[n+1];
    rank = new int[n+1];
    size = new int[n+1];
    for (int i = 1; i <= n; i++) {
      parent[i] = i;
      rank[i] = 0;
      size[i] = 1;
    }
  }

  public int find(int x) {
    assert (0 < x && x < parent.length) : "IndexOutOfBoundsException";
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
  }

  public void union(int x, int y) {
    assert (0 < x && x < parent.length) : "IndexOutOfBoundsException";
    assert (0 < y && y < parent.length) : "IndexOutOfBoundsException";
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
      parent[x] = y;
      size[y] += size[x];
    } else {
      parent[y] = x;
      size[x] += size[y];
      if (rank[x] == rank[y]) rank[x]++;
    }
  }

  public boolean same(int x, int y) {
    assert (0 < x && x < parent.length) : "IndexOutOfBoundsException";
    assert (0 < y && y < parent.length) : "IndexOutOfBoundsException";
    return find(x) == find(y);
  }

  public int size(int x) {
    assert (0 < x && x < parent.length) : "IndexOutOfBoundsException";
    return size[find(x)];
  }
}

class MyComparator {
  private static Comparator<int[]> dictIntArray = null;
  static Comparator<int[]> dictIntArray() {
    if (dictIntArray == null) dictIntArray = (a, b) -> Arrays.compare(a, b);
    return dictIntArray;
  }

  private static Comparator<int[][]> dictIntArrayArray = null;
  static Comparator<int[][]> dictIntArrayArray() {
    if (dictIntArrayArray == null) dictIntArrayArray = (a, b) -> {
      for (int i = 0; i < a.length; i++) {
        int c = Arrays.compare(a[i], b[i]);
        if (c != 0) return c;
      }
      return 0;
    };
    return dictIntArrayArray;
  }
}

// 有理数クラス
class Rational implements Comparable<Rational> {
  long num;
  long den;

  public Rational(long num, long den) {
    assert den != 0 : "denominator is zero";
    if (den < 0) {
      num *= -1;
      den *= -1;
    }
    long g = Util.gcd(Math.abs(num), den);
    this.num = num / g;
    this.den = den / g;
  }
  public Rational(long num) {
    this(num, 1);
  }
  public static Rational of(long num, long den) {
    return new Rational(num, den);
  }
  public static Rational of(long num) {
    return new Rational(num);
  }
  public int compareTo(Rational r) {
    return Long.compare(num * r.den, den * r.num);
  }
  // toString
  public String toString() {
    return num + "/" + den;
  }
  // double
  public double doubleValue() {
    return (double) num / den;
  }
  // float
  public float floatValue() {
    return (float) num / den;
  }
  // long
  public long longValue() {
    return num / den;
  }
  // int
  public int intValue() {
    return (int) (num / den);
  }
  // 約分
  public Rational reduce() {
    long g = Util.gcd(Math.abs(num), den);
    return new Rational(num / g, den / g);
  }
  // 四則演算
  public Rational add(Rational r) {
    return new Rational(num * r.den + den * r.num, den * r.den);
  }
  public Rational sub(Rational r) {
    return new Rational(num * r.den - den * r.num, den * r.den);
  }
  public Rational mul(Rational r) {
    return new Rational(num * r.num, den * r.den);
  }
  public Rational div(Rational r) {
    return new Rational(num * r.den, den * r.num);
  }
  // 逆数
  public Rational inv() {
    return new Rational(den, num);
  }
  // 符号反転
  public Rational neg() {
    return new Rational(-num, den);
  }
  // 絶対値
  public Rational abs() {
    return new Rational(Math.abs(num), den);
  }
  // 累乗
  public Rational pow(long n) {
    return new Rational((long)Math.pow(num, n), (long)Math.pow(den, n));
  }
  public Rational pow(Rational r) {
    return new Rational((long)Math.pow(num, r.num), (long)Math.pow(den, r.num));
  }
  // 平方根
  public Rational sqrt() {
    return new Rational((long)Math.sqrt(num), (long)Math.sqrt(den));
  }
  // 立方根
  public Rational cbrt() {
    return new Rational((long)Math.cbrt(num), (long)Math.cbrt(den));
  }
  // 指数関数
  public Rational exp() {
    return new Rational((long)Math.exp(num), (long)Math.exp(den));
  }
  // 対数関数
  public Rational log() {
    return new Rational((long)Math.log(num), (long)Math.log(den));
  }
  // 三角関数
  public Rational sin() {
    return new Rational((long)Math.sin(num), (long)Math.sin(den));
  }
  public Rational cos() {
    return new Rational((long)Math.cos(num), (long)Math.cos(den));
  }
  public Rational tan() {
    return new Rational((long)Math.tan(num), (long)Math.tan(den));
  }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var n = next();
  var a = nexts(n);
  var p = nexts(n-1);
  var g = xArray("[]",n);
  for(var i = 0; i < n-1; i++){
    g[p[i]-1].push(i+1);
  }
  var ans = xArray(0,n+1);
  dfs(0,0);
  for(var i = n; i >= 0; i--){
    if(ans[i] < 0)return "-";
    if(ans[i] > 0)return "+";
  }
  return 0;
  function dfs(v,k){
    ans[k] += a[v];
    for(var i = 0; i < g[v].length; i++){
      var V = g[v][i];
      dfs(V,k+1);
    }
  }
}

Python solution:
n = int(input())
a = [*map(int, input().split())]
p = [int(i) - 1 for i in input().split()]
d = [None] * n
d[0] = 0
for i, j in enumerate(p, 1):
    d[i] = d[j] + 1
b = [0] * n
for i, j in enumerate(d):
    b[j] += a[i]
while b and b[-1] == 0:
    b.pop()
if not b:
    print(0)
elif b[-1] > 0:
    print('+')
else:
    print('-')

Ruby solution:
n = gets.to_i
a = gets.split.map(&:to_i)
p = [-1] + gets.split.map { |x| x.to_i - 1 }

dep = Array.new(n, 0)
1.upto(n-1) { |i| dep[i] = dep[p[i]] + 1 }

sum = Array.new(n, 0)
0.upto(n-1) { |i| sum[dep[i]] += a[i] }

(n-1).downto(0) do |i|
  if sum[i] < 0
    puts '-'
    return
  elsif sum[i] > 0
    puts '+'
    return
  end
end
puts '0'