Cho một xâu ký tự \(S\) gồm \(n\) chữ số \(0\), các ký tự trong xâu \(S\) được đánh số từ \(1\) đến \(n\) theo thứ tự từ trái qua phải. Xét lệnh \(Fill(i,j,c)\): Trong đó \(i, j\) là các số nguyên dương \( 1≤i≤j≤n\) và \(c\) là một chữ số thuộc \( {0, 1, 2, ...., 9}\). Điền các ký tự \(c\) vào xâu \(S\) bắt đầu tự vị trí \(i\) tới vị trí \(j\). Các chữ số mới điền vào sẽ đè lên các chữ số đang có trong xâu \(S\). Cho trước số nguyên \(k\), người ta thực hiện \(m\) lần lệnh \(Fill\) để được xâu \(S\) là biểu diễn thập phân của một số tự nhiên, hãy tìm số dư của số tự nhiên đó cho \(k\).

Input

• Dòng 1 chứa 3 số nguyên \(n, m, k ( m ≤ 10^5 ; n ≤ 10^7; k≤ 10^9)\).

• \(m\) dòng tiếp theo, dòng thứ \(p\) chứa 3 số \(i_p, j_p, c_p\) cho biết lệnh \(Fill\) thứ \(p\) là \(Fill(i_p, j_p, c_p) (1 ≤ i_p ≤ j_p ≤ n; 0 ≤ c_p ≤ 9)\).

Output:

Ghi số dư cần tìm.

Sample Input

6 3 123
4 6 5
1 3 1
3 4 9

Sample Output

30