Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

INGENI10 - Metrô engenhoso

O Rei da Logônia em breve irá inaugurar um novo e revolucionário metrô, baseado numa invenção dos Engenheiros Reais, que permite teletransporte.

O novo metrô consiste de um longo túnel com uma estação a cada quilômetro. Existem também T teletransportadores, que estão localizados em algumas das estações. Em cada estação existe um teclado com T teclas, onde cada tecla corresponde a um teletransportador. A figura abaixo ilustra um sistema de metrô com três teletransportadores localizados nas estações marcadas como A, B e C.

 

 

O metrô funciona da seguinte maneira: o usuário vai até uma estação (a estação inicial) e pressiona a tecla correspondente ao teletransportador que ele quer usar. O usuário então é teletransportado para a estação que está à mesma distância do teletransportador que a estação inicial, mas do lado oposto ao teletransportador. Mais precisamente, se a localização da estação inicial é i e o usuário pressiona a tecla correspondente ao teletransportador localizado na posição j, ele será levado à estação localizada na posição 2 x j - i. Por exemplo, se o usuário está na estação 6 e quer ir até a estação -2, ele pode usar o teletransportador C (e ir do 6 ao 10) e depois o teletransportador A (e ir do 10 ao -2).

O Rei, no entanto, sabe que é possível que não exista uma sequência de teletransportadores que leve um usuário de uma estação X até uma estação Y. Para evitar que os usuários tentem ir para um lugar inacessível, ele quer criar um programa disponível na Internet para os ajudar. O Rei quer que você escreva um programa que, dadas as posições de cada teletransportador, responda uma sequência de consultas. Para cada consulta, as estações inicial e final são dadas, e seu programa deve determinar se é possível para um usuário ir da estação inicial até a estação final.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém dois inteiros T e Q indicando, respectivamente, o número de teletransportadores (1 ≤ T ≤ 105) e o número de consultas (1 ≤ Q ≤ 10). A segunda linha contém T inteiros distintos ti indicando a posição do i-ésimo teletransportador (-107ti ≤ 107). Cada uma das Q linhas seguintes descreve uma consulta e contém dois inteiros distintos S e D indicando a posição das estações inicial e final (-107S,D ≤ 107).

O último caso de teste é seguido de uma linha contendo dois zeros.

Saída

Para cada caso de teste, imprima uma única linha contendo as respostas para as Q consultas, na mesma ordem em que as consultas aparecem na entrada e separadas por um espaço em branco. Para cada consulta, você deve imprimir um caractere 'Y' se for possível chegar ao destino a partir da estação inicial usando o metrô, ou 'N' caso contrário.

Exemplo

Entrada:
1 1
-2
-6 2
5 2
10 20 30 40 50
10 15
20 40
5 3
0 5 -3 -8 4
-1 499
4 237
-1 -591
0 0

Saída:
Y
N Y
Y N Y


Adicionado por:Wanderley Guimarăes
Data:2011-06-10
Tempo limite:0.926s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2010

hide comments
2012-07-14 05:55:43 Fernando Fonseca [ITA]
Os casos de teste estăo fracos! Se quiser ter certeza de que acertou o algoritmo, teste contra essa entrada, cuja resposta é N N:
1 1
-2
-10 2
2 1
7 10
0 64
0 0

Last edit: 2012-07-14 06:03:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.