Problema B - Solidão Inteira

O isolamento numérico é um problema recorrente na sociedade moderna. São vários os números que se encontram sozinhos e procuram companhia. Como tal, a Associação Portuguesa de Inteiros está a tentar combater este flagelo ao formar casais de números inteiros. Há exatamente N inteiros solitários no país, onde N é um número par. São eles os números de 1 a N. A API quer juntar os números em casais compatíveis e para isso precisa da tua ajuda. A compatibilidade de inteiros é uma ciência ainda pouco estudada, por isso a API tem duas estratégias pensadas.

Parte I

Alguns estudos parecem indicar que se dois inteiros a e b forem tais que a sua soma é uma unidade menos que uma potência de dois, ou seja, que a + b = 2ⁱ - 1, para algum i inteiro e positivo, então a e b formam um casal compatível. Como tal, o objetivo será emparelhar cada um dos N inteiros de forma a que a soma de cada par siga este formato.

Exemplo

Se N = 8, ou seja, temos de considerar os números 1, 2, 3, 4, 5, 6, 7 e 8, então o seguinte emparelhamento é válido:

• 7 com o 8 (soma = 2⁴ - 1 = 15)
• 1 com o 6 (soma = 2³ - 1 = 7)
• 2 com o 5 (soma = 2³ - 1 = 7)
• 3 com o 4 (soma = 2³ - 1 = 7)

Notem que há vários emparelhamentos válidos, só têm de encontrar um.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 3 grupos com restrições adicionais diferentes:

Parte II

Um outro estudo (muito controverso!) parece indicar que se dois inteiros a e b forem tais que a sua soma é um número primo, ou seja, que a + b = p, para algum primo p, então a e b formam um casal compatível. Recordem que um número primo é um número maior que 1 que é divisível apenas por 1 e por si próprio. Como tal, o teu segundo objetivo será emparelhar cada um dos N inteiros de forma a que a soma de cada par seja primo.

Exemplo

Se N = 8 então o seguinte emparelhamento é válido:

• 3 com o 8 (soma = 11)
• 4 com o 7 (soma = 11)
• 5 com o 6 (soma = 11)
• 1 com o 2 (soma = 3)

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em 3 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 6 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é igual para todas as partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro N, representando o número de inteiros. Este valor será sempre par.

Output

O output deve conter N/2 linhas, cada uma contendo dois inteiros separados por um espaço, sendo que cada par deve:

• Parte I: somar a uma unidade menos que uma potência de 2;
• Parte II: somar a um primo;

Notem que apenas têm de encontrar um emparelhamento válido, mesmo que existam vários emparelhamentos possíveis. A ordem dos números não interessa. É garantido que existe sempre pelo menos um emparelhamento válido.

Input do Exemplo 1

1
8

Output do Exemplo 1

7 8
1 6
2 5
3 4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
8

Output do Exemplo 2

3 8
4 7
5 6
1 2

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.