Generalized Programmer's Day

This problem is set on a planet whose calendar is similar in structure to Earth's, but with different numerical values. In this calendar, there are \(n\) months in a year, and the \(i\)-th month has \(a_i\) days.

We define the feature value of a date represented by month \(m\) and day \(d\) as the integer obtained by concatenating the decimal representations of \(m\) and \(d\) (without any leading zeros). For example, the feature value of March 7 is \(37\) and that of December 20 is \(1220\).

A date is called a Generalized Programmer's Day if its feature value equals a natural power of \(k\); that is, if there exists a positive integer \(p\) such that \[ \text{feature value} = k^p \] where \(p\ge 1\). Note that if \(k=1\), then \(1^p=1\) for all \(p\ge 1\).

Your task is to list all the dates that are Generalized Programmer's Day on this planet.

inputFormat

The first line contains two integers \(n\) and \(k\) (1 ≤ \(n\) ≤ 10⁵, 1 ≤ \(k\) ≤ 10⁹), where \(n\) is the number of months in the year and \(k\) is the base for checking the power condition.

The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\), where \(a_i\) (1 ≤ \(a_i\) ≤ 10⁹) denotes the number of days in the \(i\)-th month.

outputFormat

For each date that is a Generalized Programmer's Day, output a line containing two integers \(m\) and \(d\) separated by a space, representing the month and the day. The dates should be listed in increasing order of month, and for the same month in increasing order of day.

If there is no such date, output a single line containing -1.

sample

2 2
5 5

-1