Il Cappellaio Matto ama offrire il suo tè verde, uno dei più pregiati al mondo.
Lo serve facendo accomodare i suoi ospiti in un tavola rotonda, i cui posti sono numerati da 1 a N in modo circolare.
Di conseguenza, i posti N e 1 risultano consecutivi.
Sfortunatamente, c’è un pegno da pagare per l’ospitalità ricevuta.
Ogni volta che il Cappellaio Matto fa squillare la sua tromba, ciascun ospite viene catapultato dal suo posto a un altro posto,
simultaneamente agli altri ospiti, secondo una tabella di mobilità M: l’ospite che siede nel posto J, viene catapultato nel posto indicato da M[J] (cioè nel posto il cui numero è scritto nella posizione J della tabella M).
Tra gli ospiti vi sono K amici: lo Stregatto li informa che dopo T squilli di tromba essi occuperanno K posti consecutivi nella tavola ma, per dispetto, non dice quali saranno questi posti.
In quell’occasione, i K amici vorrebbero circondare il Cappellaio Matto per strappargli la tromba, potendo infine degustare il tè in santa pace, ma non sanno in quali posti finiranno.
Aiuta i K amici a individuare velocemente quali posti occuperanno dopo T di squilli di tromba: poiché tali posti saranno consecutivi nella tavola, devi soltanto indicare da quale posto P in poi gli amici si troveranno.
Per esempio, vi siano N=9 ospiti, Anna, Bianca, Caterina, Daniele, Elena, Fabrizio, Giada, Hugo e Irene, in ordine crescente di posto inizialmente assegnato dal Cappellaio Matto (in realtà i nomi degli ospiti non sono rilevanti ai fini del problema).
I K=3 amici (Anna, Fabrizio, Hugo) occupano inizialmente le posizioni 1, 6 e 8; vale T=2 per la seguente tabella M di mobilità:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | posto J |
| 2 | 1 | 6 | 3 | 9 | 5 | 4 | 8 | 7 | prossimo posto M[J] |
Inizialmente, gli ospiti sono seduti come segue, dove la lettera iniziale del loro nome è riportata ai soli fini illustrativi:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| A | B | C | D | E | F | G | H | I |
Dopo il primo squillo di tromba, gli ospiti sono disposti come segue:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| B | A | D | G | F | C | I | H | E |
Dopo il secondo squillo di tromba (T=2), Hugo, Fabrizio e Anna occupano i posti consecutivi 8, 9 e 1; pertanto, bisogna restituire P=8:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| A | B | G | I | C | D | E | H | F |
Dati in Input
Il file input.txt è composto da tre righe.
La prima riga contiene tre interi N, K e T separati da uno spazio:
- N rappresenta il numero di ospiti,
- K il numero di amici che vogliono rendere innocuo il Cappellaio Matto,
- T il numero di squilli di tromba necessari affinché essi occupino posti consecutivi nella tavola.
La seconda riga contiene N numeri interi separati da uno spazio, cioè la tabella di mobilità M:
- il J-esimo intero indica il posto M[J] in cui viene catapultato l’ospite che occupa il posto J.
La terza riga contiene K interi distinti separati da uno spazio, ossia i posti inizialmente assegnati dal Cappellaio Matto ai K amici.
Dati in Output
Il file output.txt è composto da una sola riga contenente l’intero P, ossia da quale posto in poi saranno disposti consecutivamente i K amici nella tavola, dopo T squilli di tromba.
Assunzioni
- 2 <= N <= 1 000 000
- 2 <= K <= N-1
- 0 <= T <= 100 000 000
- 1 <= M[J] <= N e M[I] != M[J] per I != J (dove 1 <= I <= N e 1 <= J <= N)
- Viene sempre garantito che il valore di T soddisfa quanto richiesto dal problema.
Esempi
| input.txt | output.txt |
|---|---|
| 9 3 2 2 1 6 3 9 5 4 8 7 1 6 8 |
8 |
Note
- Il Cappellaio Matto non ha predisposto alcun posto a tavola per sè in quanto è continuamente impegnato a servire il tè ai suoi ospiti e a suonare la tromba.
- E’ ammesso che sia M[J]=J per qualche valore J, in quanto non cambia la natura del problema.
- Il Cappellaio Matto potrebbe usare una tabella Min cui, per esempio, ogni ospite viene catapultato nel posto alla sua sinistra: se gli amici non sono inizialmente vicini, allora non lo saranno mai e non esiste un valore T che soddisfa le condizioni del problema. Come precisato nelle assunzioni, situazioni simili a questa non vengono presentate come input.