Dũng thường làm gì khi anh rảnh? Như các bạn đã biết, Dũng là thành viên trẻ trâu nhất đội TNV Free Contest, vì vậy anh thường đi khắp các diễn đàn Tin học (và Toán học) để thể hiện sự trẻ trâu của mình.Dũng đã lập ra một danh sách gồm n diễn đàn mà anh thường ghé thăm, và để cho tiện, anh đánh số các diễn dàn trong danh sách bằng các số tự nhiên từ 1 đến n. Mỗi ngày, khi Dũng rảnh, anh sẽ ghé thăm một diễn đàn nào đó có số thứ tự s. Sau khi đã thể hiện sự trẻ trâu của mình tại diễn đàns, anh sẽ tiếp tục đi đến diễn đàn s + k, s + 2k, ... với k là một số tự nhiên lớn hơn 2 mà Dũng đã chọn làm số may mắn trong ngày của mình. Sau khi anh đã thăm p diễn đàn hoặc diễn đàn tiếp theo anhmuốn đến thăm có số thứ tự lớn hơn n, anh sẽ dừng lại và chuyển sang luyện các bài được đánh dấu saotrong quyển Competitive Programming 3 cho đến hết ngày.Sau d ngày, Dũng cảm thấy những bình luận trước kia của anh quá trẻ trâu (so với độ trẻ trâu hiện tại của anh), vì vậy anh cần lập kế hoạch xóa các bình luận không còn phù hợp trên các diễn đàn.Anh sẽ ưu tiên xóa các bình luận tại diễn đàn anh thể hiện sự trẻ trâu của mình nhiều lần nhất, và nếu có nhiều diễn đàn như vậy, anh sẽ ưu tiên diễn đàn có số thứ tự nhỏ nhất. Hãy viết chương trình tính số thứ tự của diễn đàn mà anh Dũng sẽ ưu tiên xóa các bình luận của mình.

Input

• Dòng đầu tiên gồm hai số nguyên dương n và d (~ 1 ≤ n, d ≤ 10^5 ~) lần lượt là số lượng diễn đàn trong danh sách và số ngày mà Dũng đã thể hiện sự trẻ trâu của mình.

• d dòng tiếp theo, mỗi dòng gồm ba số nguyên dương s, k, p (1 ≤ s ≤ n, 2 ≤ k ≤ 10, 1 ≤ p ≤ n) lần lượt là diễn đàn đầu tiên Dũng ghé thăm, số may mắn trong ngày của anh và số lượng diễn đàn tối đa mà anh muốn ghé thăm trong ngày hôm đó.

Output

• Gồm một dòng duy nhất chứa xâu "Dung can hack dien dan ~ g ~." với ~ g ~ là số thứ tự của diễn đàn mà Dũng ưu tiên xóa các bình luận của mình.

Sample

Input #1

4 3
1 2 1
3 4 2
2 2 2

Output #1

Dung can hack dien dan 1.

Input #2

10 2
2 3 2
3 2 5

Output #2

Dung can hack dien dan 5.

Problem source: Free Contest 55