Số học luôn là một lĩnh vực quyến rũ với các định lý đẹp, và đôi khi cũng nguy hiểm chết người. Có những tính chất ta nghĩ là dễ nhưng biến đổi thử mới thấy khó, nhưng đôi khi ngược lại, có những kết quả khá hiển nhiên mà ta thường tìm tòi những thứ rất xa xôi.

Do biết team ICPC của H3.2 cũng rất thích số học, đặc biệt là những bài đố mẹo, đố vui nên hôm nay, thầy Luna có giới thiệu một bài như sau: cho số nguyên dương ~n, m~, hỏi số ~n^{m!}~ thì chia cho ~2024~ dư mấy? Bạn hãy thử sức với bài toán đố vui này nhé.

Input

Một dòng duy nhất gồm hai số nguyên dương ~n, m~ với ~1 \le n, m \le 10^{18}~.

Output

Kết quả của bài toán.

Sample input 1

3 2

Sample output 1

9

Sample input 2

2023 100000

Sample output 2

1

Subtasks

• Có 25% test ứng với ~n, m \le 15~.
• Có 25% test ứng với ~m \le 15~.
• Có 50% test với giới hạn tùy ý.

Một mùa thi bận rộn và tràn đầy hy vọng lại đến. Năm nay, thầy Tina sẽ dẫn đội tuyển Olympic Tin học của IUH thi Olympic Tin học Sinh viên Việt Nam lần thứ 32 kết hợp cùng với Kỳ thi lập trình sinh viên Quốc tế ICPC Asia Huế sẽ được tổ chức tại Đại học Khoa học Huế. Một vấn đề giống với mọi năm về trước chính là làm sao chụp được một bức hình cả đội tuyển thật đẹp, để làm được như vậy thì một điều quan trọng chính là cách xếp hàng sao cho có tổ chức và đồng đều giữa các thành viên. Biết n vị trí có thể sắp hàng, thầy Tina sẽ đưa ra k yêu cầu cho các sinh viên của mình, yêu cầu thứ i (~ 1 \le i \le k ~) sắp ~c_i~ sinh viên từ vị trí ~p_i, p_i + v_i, p_i + 2 * v_i, ..., p_i + (c_i - 1) * v_i~.

Tuy nhiên vì số lượng sinh viên năm này quá đông và thầy không thể nào nhớ hết những yêu cầu trước đó. Hãy giúp thầy Tina tính xem sau yêu cầu cuối cùng thì có bao nhiêu sinh viên mỗi hàng.

Input

Dòng đầu tiên gồm 2 số n và k (~ 1 \le n, k \le 2*10^5 ~) - số vị trí có thể sắp hàng và số yêu cầu.

Tiếp theo k dòng gồm 3 số ~ c_i, p_i, v_i ~ (~ 1 \le p_i + (c_i - 1) * v_i \le n ~) -

Subtask 1: (30% số điểm) ~ 1 \le n, k \le 2*10^3 ~

Subtask 2: (35% số điểm) ~ 1 \le n, k \le 2*10^5 ~, tất cả các giá trị ~v_i~ giống nhau

Subtask 3: (35% số điểm) Không có hạn chế gì thêm.

Output

In ra kết quả gồm một dòng có n số - số sinh viên trong hàng thứ i

Examples

Input

10 3 
4 2 2 
3 2 3 
5 4 1 

Output

0 2 0 2 2 2 1 3 0 0 

*Giải thích: *

Hàng thứ 1 gồm các sinh viên theo yêu cầu: []

Hàng thứ 2 gồm các sinh viên theo yêu cầu: [1, 2]

Hàng thứ 3 gồm các sinh viên theo yêu cầu: []

Hàng thứ 4 gồm các sinh viên theo yêu cầu: [1, 3]

Hàng thứ 5 gồm các sinh viên theo yêu cầu: [2, 3]

Hàng thứ 6 gồm các sinh viên theo yêu cầu: [1, 3]

Hàng thứ 7 gồm các sinh viên theo yêu cầu: [3]

Hàng thứ 8 gồm các sinh viên theo yêu cầu: [1, 2, 3]

Hàng thứ 9 gồm các sinh viên theo yêu cầu: []

Hàng thứ 10 gồm các sinh viên theo yêu cầu: []

Để đạt mục tiêu giải cao trong kỳ thi Olympic Tin học sinh viên Tina đã học tập và cày code rất chăm chỉ, code 25 tiếng một ngày. Một hôm, sau khi accept được một câu chuỗi rất hay, Tina đã đem câu đó đi đố Luna. Cho một chuỗi gồm các chữ cái viết thường ~s~, hỏi có bao nhiêu xâu con đối xứng trong đoạn ~s[l, r]~. Tuy nhiên Luna đang bận tương tư nên chỉ nhớ tên người nào đó mà không nhớ gì về chuỗi s. Bạn hãy giúp Luna trả lời các câu hỏi này nhé.

Một xâu được gọi là đối xứng nếu nó đọc từ trái sang phải hay từ phải sang trái đều giống nhau.

Input

• Dòng đầu tiên là số lượng ký tự n của xâu ~s~.
• Dòng thứ hai gồm các ký tự chuỗi ký tự viết thường ~s~.
• Dòng thứ ba là số lượng truy vấn q
• Tiếp theo là ~q~ dòng, mỗi dòng gồm 2 số nguyên ~l, r~.

Subtasks

• Subtask 1: ~ 1 \le |s| \le 300, 1 \le q \le 15 ~
• Subtask 2: ~ 1 \le |s| \le 3000, 1 \le q \le 5 ~
• Subtask 3: ~ 1 \le |s| \le 3000, 1 \le q \le 10^6 ~

Output

In ra kết quả gồm ~q~ dòng tương ứng kết quả truy vấn.

Examples

*Input 1 *

7
ababcba 
3
1 3 
2 5
3 7

*Output 1 *

4 
5 
7 

*Input 2 *

10
hikbwhwbki
7
5 7
5 7
4 8
4 9
1 1
5 7
3 9

*Output 2 *

4
4
7
8
1
4
10

IUHCoder là một công ty khởi nghiệp còn nhiều vấn đề về nhân sự cần giải quyết. Hiện tại, công ty đang có n nhân viên. Sơ đồ mối quan hệ của các nhân viên là đồ thị cây n-1 mối quan hệ thân thiết. Biết rằng chủ tịch Hội đồng quản trị Tina đang cần tìm một giám đốc cho công ty để tăng hiệu quả quản trị. Gọi thời gian truyền tin là tổng thời gian truyền tải thông tin từ giám đốc đến tất cả nhân viên còn lại, hai nhân viên có mối quan hệ thân thiết với nhau sẽ mất 1 đơn vị thời gian để truyền tải thông tin cho nhau. Rõ ràng là thời gian truyền tin cảng nhỏ thì hiệu quả càng cao.

Hiện tại vị trí giám đốc đang do nhân viên thứ 1 trong công ty đảm nhận. Sếp Tina có thể chuyển vị trí giám đốc cho một nhân viên có quan hệ thân thiết với giám đốc hiện tại (ban đầu là nhân viên 1) và mất c đơn vị thời gian để quyết định chọn hay không, đồng thời hiệu thời gian truyền tin cũng có thể tăng học giảm tuy vào chất lượng mỗi quan hệ của nhân viên đó. Vì công ty IUHCoder đang ngày một phát triển, số lượng người làm trong công ty quá lớn và Tina đang có rất nhiều công việc cũng quan trọng không kém. Bạn là một nhân viên xuất sắc trong công ty, hãy tính tổng thời gian Tina chọn đựọc một nhân viên làm giám đốc và thời gian truyền tin đến tất cả các nhân viên còn lại là ít nhất.

Input

Dòng đầu tiên gồm 2 số n và (~ 2 \le n \le 2.10^5, 1 \le c \le 10^2 ~) - số nhân viên của công ty và thời gian để quyết định chọn một nhân viên làm giám đốc hay không.

Tiếp theo n-1 dòng gồm 2 số u và v (~ 1 \le u, v \le n ~) - hai nhân viên thứ u và v có mối quan hệ thân thiết với nhau.

Subtask 1: (40% số điểm) ~ 1 \le n \le 2.10^3 ~

Subtask 2: (15% số điểm) ~ 1 \le n \le 2.10^5 ~, với mối quan hệ thứ i (~1 \le i \le n-1~) thõa u = i, v = i + 1

Subtask 3: (45% số điểm) Không có ràng buộc gì thêm.

Output

Một dòng duy nhất là tổng thời gian Tina chọn đựọc một nhân viên làm giám đốc và thời gian truyền tin đến tất cả các nhân viên còn lại là ít nhất.

Examples

Input

6 2
1 2
2 4
4 5
4 6
2 3 

Output

9

*Giải thích: * Phương án tối ưu nhất là chọn nhân viên thứ 2 làm giám đốc, mất 2 đơn vị thời gian để Tina quyết định và 1 + 0 + 1 + 1 + 2 + 2 để truyền tin cho các nhân viên còn lại. Tổng thời gian cần thiết là 9.