C - Fishbones Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

アーティストの高砂君は、魚の骨をかたどったオブジェを作りました。

オブジェは N 本の肋骨と 1 本の脊椎からなります。 肋骨には 1 から N までの番号が付けられています。

高砂君は、以下の条件をすべて満たすように N+1 本の骨に 1 つずつ文字列を書こうと考えています。

  • 脊椎に書く文字列の長さは N である。
  • 肋骨 i = 1, \dots, N に対して、以下が成り立つ。
    • 肋骨 i に書く文字列の長さは A_i である。
    • 肋骨 i に書く文字列の B_i 文字目は、脊椎に書く文字列の i 文字目に一致する。
  • N+1 本の骨に書く文字列はいずれも、S_1, \cdots, S_M のいずれかである(重複してもよい)。

S_1, \cdots, S_M は英小文字からなる文字列であり、互いに異なります。

j = 1, \cdots, M に対して、以下の質問に答えてください。

  • 条件を満たす書き方のうち、脊椎に書く文字列が S_j であるものは存在しますか？

制約

  • N は整数
  • 1 \leq N \leq 10
  • A_i, B_i は整数 (1 \leq i \leq N)
  • 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
  • M は整数
  • 1 \leq M \leq 200\,000
  • S_j は英小文字からなる文字列 (1 \leq j \leq M)
  • 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
  • S_1, \cdots, S_M は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
\vdots
A_N B_N
M
S_1
\vdots
S_M

出力

M 行出力せよ。

j 行目 (1 \leq j \leq M) には、条件を満たす書き方のうち脊椎に書く文字列が S_j のものが存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例 1

Yes
Yes
No
No
No
No
No
No

肋骨 1,2,3,4,5 にそれぞれ chris, retro, tuna, retro, cod と書くことで、脊椎に retro を書いたときに条件を満たします。

  • retro の長さは 5 文字。
  • 各肋骨について、以下が成り立つ。
    • 肋骨 1 に書かれる文字列 chris の長さは 5 文字である。その 3 文字目は r であり、retro の 1 文字目に一致する。
    • 肋骨 2 に書かれる文字列 retro の長さは 5 文字である。その 2 文字目は e であり、retro の 2 文字目に一致する。
    • 肋骨 3 に書かれる文字列 tuna の長さは 4 文字である。その 1 文字目は t であり、retro の 3 文字目に一致する。
    • 肋骨 4 に書かれる文字列 retro の長さは 5 文字である。その 1 文字目は r であり、retro の 4 文字目に一致する。
    • 肋骨 5 に書かれる文字列 cod の長さは 3 文字である。その 2 文字目は o であり、retro の 5 文字目に一致する。

肋骨 1,2,3,4,5 にそれぞれ itchy, chris, rock, itchy, ash と書くことで、脊椎に chris を書いたときに条件を満たします。

入力例 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例 2

Yes
Yes
Yes
No
No
No
No
No

Score : 300 points

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

  • The length of the string written on the spine is N.
  • For each rib i = 1, \dots, N, the following hold.
    • The length of the string written on rib i is A_i.
    • The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
  • Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

  • Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

  • N is an integer.
  • 1 \leq N \leq 10
  • A_i and B_i are integers. (1 \leq i \leq N)
  • 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
  • M is an integer.
  • 1 \leq M \leq 200\,000
  • S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
  • 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
  • S_1, \cdots, S_M are pairwise distinct.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
\vdots
A_N B_N
M
S_1
\vdots
S_M

Output

Output M lines.

The j-th line (1 \leq j \leq M) should contain Yes if there exists a way to write strings satisfying the conditions with S_j written on the spine, and No otherwise.

Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

  • The length of retro is 5.
  • For each rib, the following hold.
    • The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
    • The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
    • The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
    • The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
    • The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.

Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No