Problem D
Låttexter

Det är välkänt att informationsinnehållet i moderna låttexter inte är särskilt högt.¹ Vi kan representera en text genom en samling variabler, där varje variabel antingen motsvarar en teckensträng eller en sammansättning av två tidigare variabler. Den slutgiltiga texten ges då av värdet på den sista variabeln.

PO-ledningen vill nu veta, för $Q$ olika värden på $R$, vilket det $R$:te tecknet i låttexten är.

Indata

På första raden står två heltal $N$ ($1 \leq N \leq 500\, 000$) och $Q$ ($1 \leq Q \leq 80\, 000$).

Sedan följer $N$ rader, vardera innehållande något av följande två alternativ:

• En nolla och sedan ett ord: 0 <ett ord> (högst $10$ tecken i ordet, enbart a-z) om variabeln representerar ett enkelt ord.

• Två heltal A och B, numren på de konkatenerade strängarna ($1 \leq A, B < $ nuvarande radnummer). Detta är alltså ett ord som skapas av två sammanslagna tidigare ord.

Därefter kommer $Q$ rader med ett heltal $R$ per rad ($1 \leq R \leq \min (10^{18},$ längd på strängen$))$, numren på de tecken vi är intresserade av.

Utdata

En enda rad med $Q$ tecken, de utplockade tecknen.

Exempel

I det första indataexemplet så får vi först ordet "hej". Sedan kommer en rad som slår ihop ordet med sig självt, så vi har nu "hejhej". Tecken 3 och 4 i strängen är "jh".

Delpoäng

I det här problemet kan du samla en del av poängen utan att lösa problemet fullständigt.

• För $20$ poäng så kommer $N$ vara maximalt $5\, 000$, $Q$ vara maximalt $10\, 000$, och alla strängar som bildas vara högst $10^{18}$ tecken långa.

• För ytterligare $60$ poäng så kommer så kommer alla strängar vara högst $10^{18}$ tecken långa.

2 2
0 hej
1 1
3
4

jh

10 3
0 a
0 b
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
10
11
12

bba