{"code":"specialnumber","name":"Số Đặc Biệt Thứ K","description":"Cho một dãy số nguyên dương vô hạn $A_1, A_2, ... A_N$ có một trong hai tính chất như sau (hoặc là có cả hai) :\r\n - Tổng các chữ số của $A_i$ chia hết cho $m$.\r\n - Chữ số cuối cùng của $A_i$ là $p(0 \\le p \\le 9)$.\r\n - Và với mọi $i > 0$ thì $a_{i} > a_{i - 1}$.\r\n\r\n***Yêu cầu*** : Hãy in ra số thứ $K$ trong dãy $A$ và cho biết phần dư của $\\sum_{i = 1}^k A_i$ khi chia cho $10^9 + 9$, **Đề bài đảm bảo $a_{K} \\le 10^{18}$**.\r\n\r\n<h4>Input</h4>\r\n\r\n - Dòng đầu tiên là một số nguyên dương $T(T \\le 81).$\r\n - $T$ dòng tiếp theo, mỗi dòng gôm 3 số nguyên $K,m,p$ với $(K \\le 10^{18}, m \\le 200, 0 \\le p \\le 9)$ .\r\n\r\n<h4>Output</h4>\r\n\r\n- Gồm $T$ dòng, mỗi dòng gồm 2 số nguyên là đáp án của dòng truy vấn tương ứng.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        3\r\n        16 8 9\r\n        42 13 6\r\n        28 32 1\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        79 668\r\n        266 6000\r\n        271 3808\r\n        ```\r\n    \r\n    ??? warning \"Note\" \r\n        **Giải thích : **\r\n        Trong lần thử nghiệm đầu tiên ta có dãy A là : 8 9 17 19 26 29 35 39 44 49 53 59 62 69 71 79 ...\r\n        Vậy số thứ 16 là số 79 và 8 + 9 + 17 + 19 + ... + 79 = 668.","points":600.0,"partial":true,"time_limit":6.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}