一个幸运转盘有 $n$ 个扇区，按顺时针方向编号为 $0$ 到 $n-1$。转盘上有一个指向某个扇区的箭头。目前，箭头指向扇区 $x$。

你非常擅长转动转盘。具体来说，你学会了 $K$ 种不同的强力转法，其力度分别为 $k_1, k_2, \dots, k_K$。力度为 $p$ 的强力转法意味着你转动转盘，使箭头顺时针转动恰好 $p$ 个扇区：形式化地讲，如果当前在扇区 $y$，转动后将指向扇区 $(y + p) \pmod n$。此外，你还可以进行普通转法：转动转盘，使箭头指向一个均匀随机的扇区。你的技能允许你以任意顺序进行任意次数的任意转法。

你希望箭头尽快指向扇区 $0$。请找出在最优策略下，达到该目标所需转动次数的期望值。如果一个策略能使该期望值最小化，则称其为最优策略。

输入格式

第一行包含三个整数：扇区数量 $n$，箭头的起始扇区 $x$，以及强力转法的数量 $K$ ($1 \le n \le 10^5$; $0 \le x \le n - 1$; $1 \le K \le 500$)。

第二行包含 $K$ 个不同的整数 $k_1, k_2, \dots, k_K$ ($1 \le k_i \le n$)。

输出格式

输出一行，包含两个整数 $p$ 和 $q$ ($0 \le p$; $0 < q$)，表示期望转动次数的最简分数 $p/q$ 的分子和分母。可以证明答案一定能表示为这种形式。

样例

输入 1

6 3 2
2 4

输出 1

8 3

输入 2

5 4 1
1

输出 2

1 1