Problema C - Sopa de Primos

Concerteza que já conheces o famoso quebra-cabeças chamado "Sopa de Letras" que envolve procurar palavras numa matriz cheia de letras. Pois bem, o editor de uma revista matemática resolveu criar um puzzle parecido chamado "Sopa de Primos", um problema que tem mais a ver com o tema da revista.

A ideia é termos uma matriz de algarismos e procurarmos nessa matriz quais os números primos menores ou iguais um determinado valor que aparecem. Recorda que um número primo é um número inteiro maior que um apenas divisível por um e por si próprio. Os números pode ser obtidos na horizontal (da direita para a esquerda ou da esquerda para a direita), na vertical (de cima para baixo ou de baixo para cima) ou na diagonal (também neste caso em qualquer um dos sentidos). A título de exemplo, na matriz a seguir representada podemos obter 10 primos diferentes menores que 65:

1234      1234 1234 1234 1234 1234 1234 1234 1234 1234 1234
5678      5678 5678 5678 5678 5678 5678 5678 5678 5678 5678
9888      9888 9888 9888 9888 9888 9888 9888 9888 9888 9888
          
Primo:      2    3    5    7   23   37   43   47   59   61

O Problema

A tua tarefa é escrever um programa para resolver uma dada sopa de primos, ou seja, encontrar todos os primos menores ou iguais a um determinado valor que surgem na "sopa".

Input

Na primeira linha do input vem um inteiro P representando o limite máximo dos números primos a considerar (0 < P ≤ 1000000). Recorda portanto que só nos interessam os primos menores ou iguais que P.

Segue-se uma linha contendo dois números inteiros separados por um espaço, L e C, que representam respectivamente o número de linhas e de colunas da matriz a considerar (0 < L,C &le 500).

De seguida vêm L linhas, cada uma contendo C dígitos (de 1 a 9), indicando a matriz propriamente dita.

Output

O output deve ser uma lista ordenada (de forma crescente) dos primos inferiores ou iguais a P encontrados na matriz. Deve vir um número primo por cada linha.

Exemplo de Input

65
3 4
1234
5678
9888

Exemplo de Output

2
3
5
7
23
37
43
47
59
61

Selecção dos Concorrentes Portugueses
Olimpíadas Internacionais de Informática 2005

(12 de Agosto de 2005)