As a new CS graduate, your friend has memorized the Fizz Buzz problem and has his first interview today. Unfortunately for him, the interviewer thought that Fizz Buzz was too easy. He has proposed a new version, as shown:

You are given a number $M$, the number of numbers you should check divisibility by, and $N$, the number you should go up to.

The next $M$ lines will contain a number $d_i$, and its associated word $w_i$.

Counting from $1$ to $N$, print the associated word(s) $w_i$ in increasing order of $d_i$ if the current number is divisible by any of the numbers $d_i$; otherwise, print the current number.

Your friend is panicking because he only memorized the $3$ and $5$ version. He is now sitting in the washroom, asking you for help. Can you help him?

Constraints

$1\le d_i\le N$

It is guaranteed that all $d_i$ will be unique.

All words $w_i$ are between $1$ and $10$ characters in length, inclusive, and only contain uppercase and lowercase letters.

Subtask 1 [10%]

$M=2$

$M\le N\le 100$

All $d_i$ will be in increasing order.

Subtask 2 [20%]

$2\le M\le 10$

$M\le N\le 100000$

Subtask 3 [70%]

$2\le M\le 10000$

$M\le N\le 100000$

Input Specification

The first line contains two space-separated integers, $M$ and $N$.

The next $M$ lines contain $d_i$ and $w_i$ separated by a space.

Output Specification

Print the required sequence of words and numbers, with one item on each line.

Sample Input 1

2 10
2 Fizz
3 Coke

Sample Output 1

1
Fizz
Coke
Fizz
5
FizzCoke
7
Fizz
Coke
Fizz

Sample Input 2

3 7
2 Fizz
6 Pepsi
3 Coke

Sample Output 2

1
Fizz
Coke
Fizz
5
FizzCokePepsi
7