题目描述

你有一棵树，根为 $1$，有 $n$ 个结点，第 $i$ 个结点有八个属性 $a_{i,1},a_{i,2},\ldots,a_{i,8}$。

请计算有多少对 $(i,j)$，结点 $i$ 是结点 $j$ 的祖先，并对所有 $k=1,2,\ldots,8$，$a_{i,k}< a_{j,k}$。

输入格式

输入的第一行有一个整数 $n$，表示树的结点数。

之后 $n$ 行，每行 $8$ 个整数 $a_{i,1},a_{i,2},\ldots,a_{i,8}$，表示八个属性值，中间没有空格隔开。

之后一行 $(n-1)$ 个整数，第 $i$ 个整数 $fa_{i+1}$ 表示结点 $i+1$ 的父亲。输入保证可以构成一棵树。

输出格式

一行一个整数，表示符合条件的 $(i,j)$ 数量。

样例 #1

样例输入 #1

4
11111111
22332233
13331333
11211112
1 1 2

样例输出 #1

1

提示

【样例解释】

$(1,2)$ 符合题意。$(1,3)$ 中 $k=1,5$ 不符题意；$(4,2)$ 中 $4$ 不是 $2$ 的祖先。

【数据范围】

• 对于“一条链”，保证 $fa_i=i-1$。
• 对于“树随机生成”，保证 $fa_i$ 在 $[1,i-1]$ 内均匀随机选取。
• 对于“周期为 $4$”，保证 $a_{i,5}=a_{i,1},a_{i,6}=a_{i,2},a_{i,7}=a_{i,3},a_{i,8}=a_{i,4}$。
• 测试点 $14\sim 16$ 中，$a_{i,k}$ 等于 $1,2,3,4,5$ 的概率比为 $1:2:2:2:1$，且整个矩阵 $a$ 任意两个数独立。

提示：你可以通过 $n$ 的个位判断该测试点类型。

对于全部数据，保证 $2\le n\le 2\times 10^5,1\le a_{i,k}\le 5$，$fa$ 构成一棵树。