Minimum Starting Sensitivity

Developers are testing a robot on a circular arrangement of m platforms (indexed from 0). Each platform i has a sensitivity value a[i] associated with it. When the robot starts at a platform, it uses that platform’s sensitivity as its starting sensitivity and makes n jumps in a circular manner. In every jump the robot moves forward by exactly a[i] platforms (where i is the starting platform) in a modular arithmetic fashion (i.e. the next platform is computed as (current_index + a[i]) mod m). The experiment is considered successful if the robot returns to its starting platform exactly after n jumps; mathematically, this condition is satisfied if

$$n\times a[i]\equiv 0\pmod m$$

Your task is to help the developers determine the minimum starting sensitivity among all platforms that yield a successful experiment, and report the index of the corresponding platform. If there are multiple platforms with the same minimum sensitivity meeting the criteria, choose the one with the smallest index.

inputFormat

The input consists of two lines:

• The first line contains two integers n and m, where n is the number of jumps and m is the total number of platforms.
• The second line contains m integers: a[0], a[1], ..., a[m-1] representing the sensitivity values of the platforms.

outputFormat

Output two space‐separated integers:

• The minimum starting sensitivity among the platforms for which the robot returns to its starting platform after n jumps.
• The corresponding platform index (0-indexed). If more than one platform qualifies with the same minimal sensitivity, output the smallest index.

Note: A platform i is valid if and only if $$n \times a[i]\equiv 0 \pmod m.$$

sample

3 6
4 1 2 5 2 3

2 2