Portales interdimensionales P56361

En el año xx42, científicos humanos descubrieron una tecnología extraña (extraterrestre, posiblemente) que era capaz de crear portales que comunicaban todas las dimensiones del universo entre ellas. Tras realizar largas investigaciones, descubrieron que las dimensiones podían numerarse de la 1 a la $N$, y que los portales sólo servían para viajar de una dimensión $i$ a la dimensión anterior $i-1$ o a la siguiente $i+1$.

Para crear el portal entre dos dimensiones era necesario disponer de un dispositivo de determinada PIU (potencia interdimensional universal). En particular, descubrieron que cada dimensión tiene un nombre (formado por como mucho 10 letras mayúsculas de la A a la Z), del cual puede extraerse un peso (la suma de los valores de las letras, desde A=1 hasta Z=26), y que la PIU para viajar entre dos dimensiones adyacentes es el valor absoluto de la diferencia de sus respectivos pesos. Por ejemplo, para viajar entre dos dimensiones consecutivas de nombre ABZ (peso $1+2+26=29$) y CACA (peso $3+1+3+1=8$) es necesario una PIU de $29-8=21$.

Sabiendo los nombres de todas las dimensiones, se te pide que escribas un programa que calcule cual es la PIU necesaria para viajar entre dos dimensiones $x$ e $y$, o sea, el máximo de las PIUs que se necesitan para crear portales entre $x$ y $x+1$, $x+1$ y $x+2$, …, $y-1$ e $y$ (si se diera el caso que $x\le y$). Tu programa deberá responder a varias de estas preguntas, y deberá tener en cuenta que, ocasionalmente, los nombres de las dimensiones cambian.

Entrada

Dos enteros $N$ y $Q$, con el número de dimensiones y el número de instrucciones que recibirá tu programa. A continuación, $N$ líneas con los nombres iniciales de las $N$ dimensiones, y $Q$ líneas con instrucciones de 2 tipos:

• A <x> <nombre>, con $1\le x\le N$, para indicar que la dimensión $x$ pasa a llamarse a partir de ahora <nombre>; y

• B <x> <y>, con $1\le x,y\le N$, para indicar que calcules la PIU necesaria para viajar de la dimensión $x$ a la dimensión $y$.

Salida

Para cada operación de tipo B, escribe una línea con el PIU necesario para viajar por las dimensiones del intervalo dado.

Puntuación

• TestA:   Entradas $N=2$ y $1\le Q\le 100$, como el Ejemplo 1.

• TestB:   Entradas $2\le N\le 100$ y $1\le Q\le 100$, como el Ejemplo 2.

• TestC:   Entradas $2\le N\le 5000$ y $1\le Q\le 5000$.

• TestD:   Entradas $2\le N\le 400000$ y $1\le Q\le 10000$, y no hay ninguna instrucción de tipo A (ninguna dimensión cambia de nombre).

• TestE:   Entradas $2\le N\le 400000$ y $1\le Q\le 20000$.