O fadino e seu presente

Iurgi, um jovem fadino do reino das fadas, adquiriu um lindo presente para o casamento de sua irmã e o guardou em um depósito mágico que tem em sua casa. No entanto, ele perdeu suas anotações e não sabe como encontrar a porta que guarda o presente. Como o casamento é amanhã, ele precisa encontrar o presente com urgência, e por isso pediu a estupenda ajuda de vocês, os especialistas mais capacitados para resolver esse assunto (foi Mario quem fez essa recomendação).

Iurgi, como é muito precavido, ocultou o conteúdo de cada porta segundo uma técnica usada por seu amigo Julius. A técnica consiste em deslocar cada letra do alfabeto um número fixo de posições. Por exemplo, com um deslocamento (rotação) de 3:

O alfabeto é rotacional ou circular, isto é, quando se chega ao fim do alfabeto, volta-se a começar a partir de $A$.

Iurgi colocou presentes falsos para confundir qualquer ladrão. A missão é encontrar a porta que contém a palavra regalo (“presente”, em espanhol) ou um anagrama dela. Um anagrama é uma palavra que resulta da transposição de todas as letras de outra palavra: por exemplo, grelao é um anagrama de regalo, e grellt não é um anagrama de regalo. Apenas uma porta contém a palavra correta; as demais terão variantes como regilo ou rugalo. Iurgi só precisa saber o índice da porta correta para conseguir abri-la.

Entrada

A primeira linha contém um inteiro $n$ ($1 \leq n \leq 10^6$), onde $n$ corresponde à quantidade total de portas.

A segunda linha contém uma lista com a quantidade de rotações com que o possível presente foi ocultado em cada porta. Isto é, há $n$ valores $r_i$ ($0 \leq r_i \leq 25$), que correspondem à rotação.

A terceira linha contém uma lista com o conteúdo de cada porta. Isto é, há $n$ palavras $p_i$, que correspondem ao conteúdo de cada porta. Cada palavra tem comprimento exatamente 6 e usa somente letras do ASCII inglês.

Saída

A saída deve conter um único inteiro, correspondente ao índice da porta com o anagrama de regalo.

Garante-se que existe uma única porta que contém o anagrama de regalo. Os índices das portas começam em $0$.

Notas

No exemplo, a palavra oculta em cada porta é:

• Porta 0: GUReIL

• Porta 1: LIruge

• Porta 2: GIAROl

• Porta 3: orgIla

• Porta 4: RoiUlG

• Porta 5: gRElao

• Porta 6: LgIURo

• Porta 7: rIlgUe

• Porta 8: gRLAoi

• Porta 9: LgIeUr

De todas as portas, a porta cinco, jUHodr, tem valor de rotação igual a 3 e, depois de decodificá-la, obtém-se a palavra gRElao, que, ordenando suas letras e ignorando maiúsculas, é regalo; isto é, ela contém as letras necessárias para formar a palavra regalo.

10
1 9 8 4 14 3 3 21 3 12
HVSfJM URadpn OQIZWt svkMpe FcwIzU jUHodr OjLXUr mDgbPz jUODrl XsUqGd

5