#P5270. 无论怎样神树大人都会删库跑路

无论怎样神树大人都会删库跑路

题目背景

众所周知,神J(Joker)每隔几天就会去成都法中假装上课,实际上是去玩指针。神J可以趁别人不注意掏出指针把自己指到任何位置(生物标本柜里大变活人?),或者把两个人的指针交换一下(成都法中版《你的名字》?),或者对着OJ念系统命令使得OJ随机变慢(mcfx:怎么这CPU睿频后反而变慢了)。

神树大人很不满意,因为树必须站在原地,而且神树大人也不会指针。但是神树大人是神,于是他打算把这个宇宙的数据库删了跑路,这样无所事事的神J就只能和神树大人玩牌了。

题目描述

现在有个长为TT的字符串SSnn个小字符串aia_i

给定一个长为mm的数组RR,数组下标从1开始,初始有一个空字符串XX,神树大人打算进行QQ次操作,第ii次操作会把小字符串aR(i1)modm+1a_{R_{(i-1)\mod m+1}}丢到这个XX的末尾。

每次操作后,神树大人会检查这个字符串XX是否存在一个后缀使得任意排列后可以变成SS

问有多少次这个字符串XX存在一个后缀使得任意排列后可以变成SS(即所有字符出现次数相同)。

可惜的是,这个字符串字符大小高达10510^5,所以你必须读入一个整数数组

输入格式

输入n,T,Qn,T,Q

接下来输入TT个数表示字符串SS

接下来输入nn行,每行第一个数lenlen表示长度,接下来输入lenlen个数表示这个小字符串,输入的每个数都在[0,105][0,10^5]范围内。

接下来输入mm

输入一行mm个数,表示RR

输出格式

输出答案

5 5 20
2 2 0 2 0
2 2 0
2 0 2
3 0 2 0
3 0 2 0
2 2 2
10
2 1 5 5 2 2 4 2 5 3
6
10 10 10000
0 1 1 1 0 1 1 0 0 0 
6 0 0 1 1 1 0 
6 0 0 0 0 0 0 
5 0 0 0 0 0 
4 1 0 0 0 
5 1 1 1 0 1 
2 1 1 
6 0 0 0 0 0 1 
1 0 
4 0 0 1 1 
1 1 
30
10 4 3 9 10 9 4 8 5 10 9 8 6 10 10 4 9 2 2 9 6 4 1 10 10 1 9 10 3 5 
3001

提示

样例1解释:

##数据范围

对于所有数据,n,T,m105,1Rin,Q109n,T,m\leq 10^5,1\leq R_i\leq n,Q\leq 10^9,所有小字符串的总长不超过10510^5,所有字符[0,105]\in[0,10^5]