Description

夹克老爷要和他的\(N\)个家丁一起去野炊啦！

夹克老爷准备了\(8\)种食材让大家在野炊的时候能够吃的开心；但不幸的是，由于家丁的记忆力有限，每个家丁只能携带其中的一种或者几种食材。确切的说，将家丁从左向右编号为\(1\)~\(N\)，第\(i\)个家丁能够记住的食材种类集合为\( \{ S_{i,k} \} \; (0 \leq \{ S_{i,k} \} \leq 8 ) \)。

夹克老爷现在很头疼，因为他迫切的想知道，对于一个家丁区间\([L,R]\)，从里面恰好选取K个家丁的食材集合能够恰好并为\( \{ T \} \)的方案数对 \(99824353\) (一个大质数)取模的值是多少。

作为最聪明的家丁，你能够告诉他么？夹克老爷一共会做\(M\)次询问。

本题可能涉及到大量输入，请妥善选择输入方式。对于C++，一个简单有效的方式是使用stdio.h 文件下的输入而非cstdio;VC++则不需要考虑这一点。

Format

Input

第一行两个整数\(N,M\)
接下来\(N\)行，对第\(i\)行有一个数，后面有\(| S_{i,k} |\)个数描述了这个集合
接下来\(M\)行，每行行首有三个数\(L,R,K\)，接下来有一个数\(| \{ T \} |\)，后接\(| \{ T \} |\)个数描述了这个集合
\(1 \leq N,M,K \leq 100,000\)

Output

输出\(M\)行，每行一个数
如果对某次询问不存在相应的解，你应该在相应行输出\(0\)

Sample 1

Input

2 2
2 1 2
1 1
1 2  1 1 1
1 2  2 2 1 2

Output

1
1

Limitation

1s, 512MiB for each test case.

Hint

样例解释

第一次询问只有选家丁\(2\)的时候可以满足
第二次询问只有同时选家丁\(1\)和家丁\(2\)的时候可以满足

数据范围

对于2%的数据，\(M≤5，K≤5\)；
另有8%的数据，\(K≥R-L+1\)；
另有20%的数据，\(Σ(R-L+1)^K≤30,000,000\)；
另有20%的数据，\(M<256\)；
另有20%的数据，\(M<256,K \leq 2\)；
对于100%的数据，\(1 \leq N,M,K \leq 100,000\)。

Source

CSP 2019 综合测试题（四）