Грайлдан келген пианист \(K\) пернеден тұратын пианинода ойнайды. Өмірінде ол \(N\) композиция жазды.

Әр композиция былайша анықталады: алдымен \(X\) саны жазылады — композициядағы ноталардың саны, содан кейін \(X\) сан \(p_1, p_2, \dots, p_X\) — ойнау керек пернелердің нөмірлері (әр нота — \(1\)-ден \(K\)-ға дейінгі сан).

Сіз \(Q\) сұрауға жауап беруіңіз керек. Әр сұрауда \([L, R]\) аралығы беріледі. Пианист тек \(L\)-ден \(R\)-ге дейінгі нөмірлері бар пернелерді ғана пайдалана алады. Берілген сұрау үшін, ол толық ойнай алатын әр түрлі композициялардың санын есептеңіз, яғни композицияның барлық ноталары \([L, R]\) аралығында орналасқан.

Енгізу

Бірінші жолда үш бүтін сан \(N\), \(Q\), \(K\) (\(1 \le N, Q \le 2 \cdot 10^5\), \(1 \le K \le 1000\)) жазылған.

Кейін \(N\) композициялардың сипаттамалары беріледі. Әр композицияның сипаттамасы: жеке жолда \(X\) саны (\(1 \le X\)) жазылады, содан кейін \(X\) бүтін сан \(p_1, p_2, \dots, p_X\) (\(1 \le p_i \le K\)).

\(\sum X \le 2 \cdot 10^5\) екендігіне кепілдік беріледі.

Кейін \(Q\) сұраулар беріледі. Әр сұрау екі бүтін сан \(L\) және \(R\) (\(1 \le L \le R \le K\)) арқылы анықталады.

Шығару

Әр сұрау үшін бір бүтін сан шығарыңыз — \(L\)-ден \(R\)-ге дейінгі пернелерді пайдаланып ойнауға болатын композициялардың саны.

Мысалдар

Енгізу 1

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

Жауап 1

0
1
1
0

Ескертпелер

Сұрауда ешқандай композиция сәйкес келмейді: бірінші композицияда 5 нота бар, екінші композицияда 4 нота бар, үшінші композицияда 5 нота бар, олардың барлығы сәйкес келмейді. Сондықтан жауап 0.

Сұрауда тек екінші композиция сәйкес келеді, өйткені екі нотаның да диапазонда; бірінші және үшінші композициялар 5 нотасы (және бірінші композицияда 1 нота да бар) себепті сәйкес келмейді. Сондықтан жауап 1.

Сұрауда тек үшінші композиция сәйкес келеді; бірінші композиция 1 және 3 ноталары себепті сәйкес келмейді, ал екінші композиция 2 нотасы себепті сәйкес келмейді. Сондықтан жауап 1.

Сұрауда ешқандай композиция сәйкес келмейді, өйткені барлық композицияларда 3-ке сәйкес келмейтін ноталар бар. Сондықтан жауап 0