Problem B
#include "main.hpp"

Louise har tillbringat det senaste året med att förbereda sig för en kommande programmeringstävling. Intressant nog tillåter denna tävling endast deltagare att använda ett forntida programspråk kallat H++.

I H++, som är ett objektorienterat språk, kan man inkludera externa filer i sitt program under kompileringen genom att skriva raden:

#include "file.hpp"

När kompilatorn stöter på denna rad inkluderar den innehållet från den angivna filen (file.hpp) i den aktuella filen på platsen där #include-direktivet finns. Innehållet i file.hpp kopieras och klistras in där #include-kommandot finns, vilket ersätter den raden i filen.

En viktig egenskap hos H++ är att filer kan inkludera sig själva. Det innebär att om en fil som heter main.hpp innehåller en rad som:

#include "main.hpp"

innebär det att filen main.hpp kommer inkluderas rekursivt, där innehållet i main.hpp kopieras och klistras in igen. Detta skapar en självreplikerande cykel som kan upprepas flera gånger, vilket potentiellt resulterar i en väldigt stor fil. För att förhindra detta från att bli en oändlig loop introducerade skaparen av H++ en rekursionsgräns, som låter användaren sätta ett maximalt antal rekursiva inkluderingar (betecknat som $k$).

Detta innebär att om filen befinner sig på den $k$-te rekursionsnivån, kommer den endast att inkludera raden #include "main.hpp" på den specifika nivån av filen. Efter $k$ lager av inkluderingar stoppas rekursionen.

När filen kompileras tilldelas varje rad i den resulterande filen ett unikt radnummer, där första raden har radnummer 1.

Men när Louise försöker använda denna funktion stöter hon på många kompileringsfel. Specifikt får hon $Q$ kompileringsfel, var och en anger ett radnummer i den slutliga kompilerade filen där ett fel inträffade. Dessa radnummer motsvarar den kompilerade filen, där innehållet från main.hpp har kopierats flera gånger på grund av de rekursiva inkluderingarna.

Problemet är att dessa radnummer är baserade på den kompilerade versionen av filen, inte den ursprungliga filen. Som ett resultat behöver Louise hjälp att ta reda på vilka felraderna i den kompilerade filen faktiskt motsvarar i den ursprungliga koden.

Indata

Den första raden innehåller tre heltal $N$, $k$ och $Q$ ($1 \leq N \leq 10^6$, $1 \leq k \leq 10^9$, $1 \leq Q \leq 10^5$). $N$ är antalet rader i den ursprungliga filen main.hpp, $k$ är rekursionsgränsen (det maximala antalet rekursiva inkluderingar), och $Q$ är antalet kompileringsfel.

De följande $N$ raderna innehåller varje en rad kod från main.hpp. Var och en av dessa rader består av högst 35 utskrivbara ASCII-tecken. main.hpp kommer inte att inkludera andra filer än main.hpp.

De följande $Q$ raderna innehåller var och en ett heltal $p_i$ ($1 \leq p_i \leq 10^{12}$), vilket indikerar ett radnummer i den kompilerade filen där ett fel uppstod. Det är garanterat att $p_i$ kommer att vara ett giltigt radnummer i den kompilerade filen.

OBS: Värdet på $p_i$ kommer inte att få plats i ett 32-bitars heltal, så var medveten om att det kan överflöda om du använder C++. Notera också att det finns en stor mängd indata och utdata, så det rekommenderas att använda snabb in-/utdata (IO).

Utdata

För varje av de $Q$ felen, skriv ut motsvarande kodrad från den ursprungliga filen main.hpp som motsvarar radnumret i den kompilerade filen. Utdata ska ges i samma ordning som de $Q$ felraderna anges.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall

Det första exemplet har endast 1 rad med #include "main.hpp". Rad 1, 3 och 5 i den kompilerade filen motsvarar rad 1, 3 och 5 i den ursprungliga filen. Rad 8 i den kompilerade filen motsvarar rad 4 i den ursprungliga filen. Rad 13 i den kompilerade filen motsvarar rad 5 i den ursprungliga filen.

Figure 1: Illustration av exempel 1 med ursprungligen 5 rader. De röda siffrorna visar motsvarande radnummer i den kompilerade filen.

Figure 2: Illustration av den kompilerade filen i exempel 1. De röda siffrorna visar motsvarande radnummer i den kompilerade filen.

Figure 3: Illustration av exempel 3 med ursprungligen 3 rader. De röda siffrorna visar motsvarande radnummer i den kompilerade filen.

5 2 5
#include "main.hpp"
int main(){
    std::cout << "Hello World\n";
    return 0;
}
1
3
5
8
13

#include "main.hpp"
    std::cout << "Hello World\n";
}
    return 0;
}

10 3 12
#include <bits/stdH++.h>
#include "main.hpp"
#include "main.hpp"
int main(){
    int x;
    std::cin >> x;
    if (x%2) std::cout << "Odd\n";
    else std::cout << "Even\n";
    return 0;
}
13
14
15
16
17
18
19
20
21
22
23
24

}
#include <bits/stdH++.h>
#include "main.hpp"
#include "main.hpp"
int main(){
    int x;
    std::cin >> x;
    if (x%2) std::cout << "Odd\n";
    else std::cout << "Even\n";
    return 0;
}
int main(){

3 1 7
#include "main.hpp"
#include <bits/stdH++.h>
#include "main.hpp"
1
2
3
4
5
6
7

#include "main.hpp"
#include <bits/stdH++.h>
#include "main.hpp"
#include <bits/stdH++.h>
#include "main.hpp"
#include <bits/stdH++.h>
#include "main.hpp"

4 5 4
n = int(input())
a = [*map(int,input().split())]
a.sort()
print("no #include here")
1
2
3
4

n = int(input())
a = [*map(int,input().split())]
a.sort()
print("no #include here")