시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 768 MB 41 4 4 10.000%

문제

오늘날 많은 이상한 사람들이 있습니다. 우리는 가장 흥미있는 사람들의 특정 유형에 초점을 두려고 합니다.그렇습니다. 야만인에 대해 얘기하려는 겁니다.

야만인이 많이 있지만, 불과 몇 명만 정말 중요합니다. 중요한 야만인에 대해서는 1에서 N 으로 표시할 수 있습니다.그들은 알파벳 소문자로 쓰여진 자신만의 돌판을 가지고 있습니다.

우리 야만인들은 친구 타잔과 재미있는 게임을 합니다.이 게임은 Q 번의 라운드를 하며, 타잔에 의해 정해진 라운드에는 두 가지 유형이 있습니다. 

  • 첫번째 유형 : 타잔은 문자 P를 야만인들에게 보여줍니다.
  • 두번째 유형 : 타잔은 야만인들에게 다음과 같이 S개의 질문을 합니다. "이제까지 보여준 모든 단어를 제외하고 야만인들이 가진 돌판에 얼마나 많은 문자가 연속적으로 있는지?"

야만인들은 사나워질 수 있으며 게임중에 일어나는 일에 지속적으로 집중하지 못할 수 있다는 사실을 알게되었습니다.

입력

입력의 첫 번째 줄은 정수 N (1≤N≤10^5), 야만인의 수를 포함합니다.

다음 N 라인에는 영어 알파벳 소문자로만 구정된 한개의 단어가 주어지며 i번째 단어는 야만인들의 돌판위에 있는 단어를 나타냅니다. 그 아래로 게임 라운드의 횟수를 나타내는 정수 Q (1≤Q≤10^5) 가 주어집니다. 다음 Q 라인에는 각 라운드를 나타내며 i번째 라인은 i번째 라운드를 뜻한다. 각 라인은 정수 O 를 가지고 있는데 O 가 1과 같은 경우는 첫번째 유형을 말하며 같은 줄에 영어 알파벳 소문자로만 구성된 P개의 단어가 나온다. O 가 2와 같은 경우는 두번째 유형을 말하며, 숫자 S(1<=S<=N) 다음에 타잔이 질문한 야만인의 레이블이 나옵니다. 야만인의 돌판에 있는 단어의 길이는 2x10^6 을 넘지 않습니다. 타잔이 야만인에게 보여준 단어의 길이도 2x10^6 을 넘지 않습니다.

출력

다른 유형의 각각의 라운드에 대해 한줄로 표현하며 i 번째 라인에는 2번째 유형의 i번째 타잔의 질문에 대한 정답을 반드시 포함해야 합니다.

예제 입력

3
a
bc
abc
3
1 abca
2 1
2 3

예제 출력

1
1

예제 입력 2

7
abba
bbaa
b
bbaa
abba
a
ba
7
1 aaabbabbaab
2 7
1 baabaaa
1 aabbbab
2 3
1 aabba
2 3

예제 출력 2

1
3
4

힌트

첫번째 예제에: 타잔이 보여준 단어는 abca 이며 첫번째 질문에 대한 답은 1이다. 왜나하면 문자 a 는 abca 은 부분 문자열이다. 두번째 질문에 대한 답도 1이다. 왜냐하면 단어 abc 는 단어 abca 의 부분 문자열이기 때문이다.