有 n 道互不相同的工序，编号为 1 至 n。每道工序使用一个或两个资源。两份循环作业表 A、B 都把这 n 道工序各列出一次。

在 A 中选定起点 i，取出一轮工序，得到线性顺序：

A_i, A_{i+1}, …, A_n, A_1, …, A_{i−1}

在 B 中选定起点 j，以同样方式得到另一份线性顺序。

对取出的第一份线性顺序，你可以执行任意多次以下操作：选择两道相邻且使用的资源没有交集的工序，交换它们的位置。线性顺序的首尾不相邻，操作过程中不能重新选择起点。

求有多少个起点对 (i,j)，能使第一份线性顺序经过允许的交换后，与第二份线性顺序完全相同。只要 i 或 j 不同，就计为不同的起点对。

输入格式

本题只有一组输入数据。

第一行包含 n、k，表示工序数和资源总数。

接下来 n 行，第 u 行先给出工序 u 使用的资源数量 d_u，再给出 d_u 个资源编号。

接下来一行包含排列 A，最后一行包含排列 B。

输出格式

输出合法起点对的数量，不取模。

数据范围

• 1 ≤ n,k ≤ 200000；
• 1 ≤ d_u ≤ min(2,k)；
• 每个资源编号在 [1,k] 内，同一道工序的资源编号互不相同；
• A、B 都是 1 至 n 的排列；允许存在没有被使用的资源。

样例 1

4 2
1 1
1 1
1 2
1 2
1 2 3 4
1 2 3 4

6

说明：除四个 i=j 的起点对外，(1,3)、(3,1) 也合法。例如 1,2,3,4 可以通过允许的相邻交换变成 3,4,1,2。

样例 2

3 3
2 1 2
2 2 3
2 1 3
1 2 3
1 3 2

0

说明：任意两道工序都共用资源，无法进行任何交换。两份表任取起点，得到的顺序也不会相同。

下载样例数据