Maximize the Game Rounds

You are about to play T games with a friend. The rules for each game are as follows:

1. You choose a positive integer \(x\) in the range \(1\) to \(n\).
2. Your friend then asks you \(Q\) queries. In the \(i\)th query, he gives you an integer \(a_i\) (with \(1 \le a_i \le n\)), and you must answer with \(\gcd(x, a_i)\) (the greatest common divisor of \(x\) and \(a_i\)).
3. Right after any query, if your friend is able to uniquely determine the value of \(x\) on the basis of the answers given so far, the game immediately ends.

You have the advantage of knowing all the queries \(a_1,a_2,\dots,a_Q\) in advance. Your task is to choose an integer \(x\) from \([1,n]\) such that the game lasts as many rounds (queries) as possible. In other words, let the "round count" for a given \(x\) be the minimum index \(k\) (\(1 \le k \le Q\)) such that the sequence of answers \(\big(\gcd(x,a_1),\gcd(x,a_2),\dots,\gcd(x,a_k)\big)\) uniquely identifies \(x\) among all integers in \([1,n]\). If no prefix of the \(Q\) answers can uniquely identify \(x\), we define its round count to be \(Q\). Your goal is to choose any \(x\) that maximizes this round count. If there is a tie, choose the smallest such \(x\).

Note: Although you will play T games, the queries in each game are determined by the same sequence \(a_1, a_2, \dots, a_Q\), and you must choose a fixed \(x\) for every game.

Input/Output Format: See the sections below.

inputFormat

The first line contains three integers \(T, n, Q\) (\(1 \le T \le 10^5, 1 \le n \le 1000, 1 \le Q \le 100\)). The second line contains \(Q\) integers \(a_1, a_2, \dots, a_Q\) (each satisfying \(1 \le a_i \le n\)).

Note: The constraints are chosen so that a \(O(n\cdot Q)\) solution is acceptable.

outputFormat

Output two integers separated by a space: the chosen integer \(x\) and the number of rounds the game lasts when using this \(x\). That is, the first index \(k\) (or \(Q\) if no prefix uniquely identifies \(x\)) that results in \(x\) being uniquely identifiable among all numbers in \([1,n]\).

sample

1 10 3
2 3 4

1 3