Marathon Matrix

Cấp số nhân là một dãy số thỏa mãn điều kiện tỷ số giữa \(2\) phần tử liên tiếp là hằng số. Xét dãy cấp số nhân \(1,x,x^2,x^3,….,x^n\).

Yêu cầu: Cho 2 số nguyên \(x\) và \(n\). Tính tổng tất cả các phần tử trong cấp số nhân đã cho. Vì kết quả có thể rất lớn nên chỉ đưa ra số dư trong phép chia cho \(m\).

Input

• Một dòng chứa 3 số nguyên dương \(x,n,m \ (x \leq 100, n \leq 10^{18}, m \leq 10^7)\).

Output

• Một số nguyên là kết quả của bài toán.

Example

2 6 1000 

127

Trong toán học, tam giác Pascal là một mảng tam giác của các hệ số nhị thức. Các hàng của tam giác Pascal được liệt kê theo quy ước bắt đầu bằng hàng \(n = 0\) ở trên cùng (hàng \(0\)). Các mục trong mỗi hàng được đánh số từ đầu bên trái với \(k = 0\) và thường được đặt so le so với các số trong các hàng liền kề. Tam giác có thể được xây dựng theo cách sau: Trong hàng \(0\) (hàng trên cùng), có một số \(1\) duy nhất. Mỗi số của mỗi hàng tiếp theo được xây dựng bằng cách thêm số ở trên và bên trái với số ở trên và sang bên phải, coi các mục trống là \(0\). Ví dụ: số ban đầu trong hàng đầu tiên (hoặc bất kỳ số nào khác) là \(1\) (tổng của \(0\) và \(1\)), trong khi các số \(1\) và \(3\) trong hàng thứ ba được thêm vào để tạo ra số \(4\) ở hàng thứ tư.

Ta gọi \(P(n)=A[0,n-1]+A[1,n-2]+...+A[C(n/2)-1,n-C(n/2)]\)

Trong đó :

• \(n\) là số nhập trong input
• \(A[i,j]\) là số thứ \(i\) của hàng thứ \(j\) (Tính từ trái qua phải, số đầu tiên là số thứ 0)
• \(C(x)\) = Giá trị của \(x\) khi làm tròn lên. Ví dụ \(C(2.5) = 3\).
• \(A[i,j]\) = \(A[j,i]\)

Yêu cầu : Nhập số \(n\). Hãy xuất \(P(n)\). Bạn phải trả lời \(t\) câu hỏi

Input

• Dòng đầu nhập số \(t\) là số truy vấn \((t \leq 10^5)\)
• \(t\) dòng tiếp theo, mỗi dòng là mỗi số nguyên dương \(n\) \((n \leq 10^{18})\)

Output

• Xuất ra \(t\) dòng, mỗi dòng là kết quả \(P(n)\) tìm được. Vì \(P(n)\) có thể rất lớn nên hãy in ra \(P(n)\) chia lấy dư cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(T = 1\), \(\dfrac{1}{2}\) số test trong số này : \(N \leq 10^6\)
• Subtask \(2\) (\(60\%\) số điểm): \(T \leq 10^5\), \(\dfrac{1}{2}\) số test trong số này : \(N \leq 10^6\)

Example

2
1
2

1
1

Trong phòng họp, có \(m\) chiếc ghế xếp ngang. Có tối đa \(n\) người sẽ tham dự cuộc họp. Mỗi người sẽ ngồi một ghế hoặc hai ghế kề nhau (một ghế cho đồ dùng cá nhân). Cho trước \(m, n\), hãy xác định xem nếu có đúng \(i \ (1 \leq i \leq n)\) người thứ \(1, 2, ..., i\) tham gia cuộc họp thì có bao nhiêu cách sắp ghế cho họ. Biết rằng người \(x\) luôn ngồi phía bên trái người \(y\) nếu \(1 \leq x < y \leq i\).

Hai cách xếp được gọi là khác nhau nếu có một người ngồi ở vị trí khác nhau trong 2 cách đó.

Input

• Gồm hai số \(m, n \ (0 < m \leq 10^9, 0 < n < 2^{15})\) tương ứng là số ghế và số người tối đa sẽ tham gia.

Output

• In ra \(n\) số, số thứ \(i\) là số cách xếp ghế nếu có \(i\) người tham gia. Vì đáp số rất lớn nên các bạn hãy ra số dư của nó khi chia cho \(998244353\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, m \leq 1000\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 1000\)
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm

3 3

5 5 1

1 1

1

5 10

9 25 25 9 1 0 0 0 0 0

Một dãy FIBONACCI được định nghĩa như sau: \(F_0 = F_1 = 1\); \(F_N = F_{N-1} + F_{N-2}\) \(∀\) \(N > 1\).

Một vài phần tử đầu của dãy là: 1,1,2,3,5,8,13,21,...

Với mỗi số nguyên dương \(p\), gọi \(D_p\) là số cách biểu diễn số \(p\) dưới dạng tổng các số FIBONACCI khác nhau.

Bạn được cho một mảng \(A\) gồm \(N\) phần tử. Với mỗi giá trị \(k\) = \(1, 2, ..., N\), ta định nghĩa \(p_k\) = \(F_{A_1} + F_{A_2} + ... + F_{A_k}\). Nhiệm vụ của bạn là hãy tính \(D_{p_k}\) \(∀\) \(k\) = \(1, 2, ... , N\). Vì kết quả rất lớn nên đáp án cuối cùng là \(D_{p_k}\) modulo \(10^9+7\).

Input

• Dòng thứ nhất là số nguyên dương \(N\), số phần tử của mảng \(A\).
• Dòng thứ hai gồm các số nguyên dương \(A_1, A_2, ... , A_N\).

Output

• Gồm \(N\) dòng, mỗi dòng là \(D_{p_k}\) modulo \(10^9+7\).

Scoring

• Subtask \(1\) (\(5\%\) số điểm): \(N, A_i \leq 15\).
• Subtask \(2\) (\(20\%\) số điểm): \(N, A_i \leq 100\).
• Subtask \(3\) (\(15\%\) số điểm): \(N \leq 100\), \(A_i\) là số chính phương.
• Subtask \(4\) (\(10\%\) số điểm): \(N \leq 100\), \(A_i\) không có giới hạn gì thêm.
• Subtask \(5\) (\(15\%\) số điểm): \(A_i\) là các số chẵn.
• Subtask \(6\) (\(35\%\) số điểm): \(N \leq 10^5, A_i \leq 10^9\)

Example

4
4 1 1 5 

2
2
1
2

SPyofgame đang thực hiện một thử thách: đạt được mức Expert codeforces trong 1 tháng hoặc mất 50k. Trong lúc luyện tập, anh ấy gặp một bài toán.

Cho mảng \(A\) gồm \(N\) phần tử, phần tử thứ \(i\) có giá trị \(A[i]\). Có \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên \(L\) và \(R\). Câu trả lời cho truy vấn này là có bao nhiêu giá trị khác nhau xuất hiện chính xác 2 lần trong đoạn \([L;R]\) đó

Input

• Dòng thứ nhất chứa hai số nguyên \(N,Q\) \((1 \leq N,Q \leq 500 000)\)
• Dòng thứ hai là các số nguyên \(A[i]\) \((A[i] \leq 1 000 000 000)\)
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R \ (1 \leq L \leq R \leq N)\)

Output

• Gồm Q dòng, mỗi dòng là câu trả lời của từng truy vấn

Example

5 1
1 2 1 1 1
1 3

1

**Lưu ý: Bản này khác bản dễ ở time limit và memory limit, ai làm được có thưởng :v **

Một dãy FIBONACCI được định nghĩa như sau: \(F_{0}\) = \(F_{1}\) = 1; \(F_{N}\) = \(F_{N-1}\) + \(F_{N-2}\) \(\forall\) \(N\) > \(1\).

Một vài phần tử đầu của dãy là: 1,1,2,3,5,8,13,21,...

Với mỗi số nguyên dương p, gọi \(D_{p}\) là số cách biểu diễn số p dưới dạng tổng các số FIBONACCI khác nhau.

Bạn được cho một mảng A gồm N phần tử. Với mỗi giá trị k = 1, 2, ..., N, ta định nghĩa \(p_{k}\) = \(F_{A_{1}}\) + \(F_{A_{2}}\) + ... + \(F_{A_{k}}\). Nhiệm vụ của bạn là hãy tính \(D_{p_{k}}\) \(\forall\) k = 1, 2, ..., N. Vì kết quả rất lớn nên đáp án cuối cùng là \(D_{p_{k}}\) modulo \(10^9\) + 7

Input

• Dòng thứ nhất là số nguyên dương N, số phần tử của mảng A.
• Dòng thứ hai gồm các số nguyên dương \(A_{1}\), \(A_{2}\), ..., \(A_{N}\).

Output

• Gồm N dòng, mỗi dòng là \(D_{p_k}\) modulo \(10^9\) + 7.

Scoring

• Subtask \(1\) (\(5\%\) số điểm): N, \(A_{i}\) \(\leq\) 15.
• Subtask \(2\) (\(20\%\) số điểm): N, \(A_{i}\) \(\leq\) 100.
• Subtask \(3\) (\(15\%\) số điểm): N \(\leq\) 100, \(A_{i}\) là số chính phương.
• Subtask \(4\) (\(10\%\) số điểm): N \(\leq\) 100, \(A_{i}\) không có giới hạn gì thêm.
• Subtask \(5\) (\(15\%\) số điểm): \(A_{i}\) là các số chẵn.
• Subtask \(6\) (\(35\%\) số điểm): N \(\leq\) \(10^5\), \(A_{i}\) \(\leq\) \(10^9\)

Example

4
4 1 1 5

2
2
1
2

Bờm đang nghiên cứu mực nước biển ở hành tinh Quạt Mo. Sau nhiều ngày theo dõi, Bờm nhận thấy rằng quy luật của mực nước biển là: mực nước biển của một ngày bất kì bằng trung bình cộng mực nước biển của ngày hôm trước và ngày hôm sau. Dựa vào ghi chép mực nước biển hai ngày đầu của Bờm, hãy tính toán mực nước biển ngày thứ \(N\).

Input

• Dòng 1: chứa 2 số nguyên \(b, a\) là mực nước biển 2 ngày đầu (\(-100 \le a, b \le 100\)). Số \(a\) là mực nước ngày thứ nhất, số \(b\) là mực nước ngày thứ 2.
• Dòng 2: chứa số nguyên dương \(N\) (\(3\le N\le 10^{12}\)).

Output

• Mực nước biển ngày thứ \(N\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n\le 10^7\)
• Subtask \(2\) (\(50\%\) số điểm): \(10^7<n\le 10^{12}\)

Example

1 2
3

3

3 1
​3

-1

Cho một hình chữ nhật kích thước \(2 \times N (1\le N\le 10^9)\). Hãy đếm số cách lát các viên gạch nhỏ kích thước \(1\times 2\) và \(2\times 1\) vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Input

• Gồm nhiều test, dòng đầu ghi số lượng test \(T ( T\le 100 )\). \(T\) dòng sau mỗi dòng ghi một số \(N\).

Output

• Ghi ra \(T\) dòng là số cách lát tương ứng lấy phần dư cho 111539786.

Example

3    
1
2
3

1
2
3

Nguồn: https://vn.spoj.com/problems/LATGACH4/

Giờ học về phép chia có dư tỏ ra quá dễ dàng cho các bé trường mầm non SuperKids, để tăng tính hấp dẫn cho giờ học, cô giáo muốn đặt ra một thách thức mới.

Cho ba số nguyên dương \(x, n, m\). Cô giáo xét dãy chữ số là biểu diễn thập phân của \(x\) và viết lặp đi lặp lại dãy chữ số này \(n\) lần để được biểu diễn thập phân của một số \(y\). Nhiệm vụ của các bé là phải cho biết số dư của \(y\) khi chia cho \(m\).

Ví dụ với \(x = 12, n = 3, m = 8\). Số \(y = 121212\), số dư của \(y\) khi chia cho 8 là 4.

Các bé làm việc rất hào hứng và nhanh chóng đưa ra kết quả, vấn dề của cô giáo là cần biết kết quả đúng để phát phiếu bé ngoan cho các bé làm đúng và nhanh nhất. Em hãy giúp cô giáo tính toán kết quả.

Input

• Một dòng chứa 3 số guyên dương \(x, n, m. (x, n, m \le 10^{18})\)

Output

• Một số nguyên dương là số dư của y khi chia cho \(m\).

Example

12 3 8

4

Cho một tứ diện, đánh dấu các đỉnh lần lượt là \(A, B, C, D\).

Một con kiến ​​đang đứng trên đỉnh \(D\) của tứ diện. Con kiến ​​khá tích cực di chuyển và nó không chịu nhàn rỗi. Với mỗi bước đi, nó bước từ một đỉnh tới đỉnh khác dọc theo một số cạnh của tứ diện. Con kiến ​​không bao giờ chịu đứng yên ở một chỗ.

Yêu cầu: Đếm số cách mà con kiến ​​có thể đi từ đỉnh \(D\) ban đầu rồi quay về chính nó trong đúng \(n\) bước. Nói cách khác, bạn sẽ được yêu cầu tìm ra số con đường tuần hoàn khác nhau có chiều dài \(n\) từ đỉnh \(D\) đến chính nó. Vì số có thể khá lớn nên bạn nên in theo \(modulo (10^9 + 7)\).

Input

• Dòng đầu tiên chứa số nguyên duy nhất \(n (1 \le n \le 10^7)\) - chiều dài của đường đi.

Output

• In số nguyên duy nhất là kết quả tìm được \(modulo (10^9+ 7)\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10^7\)
• Subtask \(3\) (\(50\%\) số điểm): \(n \le 10^{14}\)

Example

2

3

Carnaval Hạ Long 2015 với chủ đề “Hội tụ tinh hoa - Lan tỏa nụ cười”, điểm mới của lễ hội là sự song hành giữa biểu diễn nghệ thuật “Nơi tinh hoa hội tụ” và diễu hành đường phố “Nụ cười Hạ Long” với sự góp mặt của hơn 2000 diễn viên quần chúng. Có rất nhiều chương trình vui chơi được tổ chức, một trong những trò chơi thu hút được nhiều du khách tham gia đó là trò chơi nhảy lò cò, cụ thể: người chơi cần vượt qua một đoạn đường dài \(n\) mét, mỗi bước, người chơi có ba cách nhảy với độ dài bước nhảy tương ứng là 1 mét, 2 mét, 3 mét. Một cách đi chuyển đúng là dãy các bước nhảy có tổng đúng bằng \(n\).

Yêu cầu: Cho \(n\) và \(M\), gọi \(K\) là số cách di chuyển đúng khác nhau để đi hết đoạn đường \(n\) mét, hãy tính phần dư của \(K\) chia \(M\).

Input

• Gồm một dòng chứa hai số nguyên dương \(n, M (M \le 20^{15})\);

Output

• Một số nguyên là phần dư của \(K\) chia \(M\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\);
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^6\);
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{15}\).

Example

5  100 

13

Cho 2 dãy \(a\) và \(b\) gồm \(n\) chữ số \(a_1\), \(a_2\), \(a_3\),... \(a_{n-1}\), \(a_n\) và \(b_1\), \(b_2\), \(b_3\),... \(b_{n-1}\), \(b_n\) (\(0 \leq a[i] , b[i] \leq 10^9\)). Một dãy C dài vô tận được xác định theo công thức sau:

• \(c_i = a_{i}\) nếu \(i \leq n\)
• \(c_i = c_{i - 1} * b_1 + c_{i - 2} * b_2 + c_{i - 3} * b_3 + ... + c_{i - n} * b_n\) nếu \(i > n\)

Yêu cầu: Tìm \(C_k\) với k là một số nguyên cho trước (\(k\) \(\leq\) \(10^9\))

Input

Dòng thứ nhất chứa số nguyên \(t\) là số lượng test ( \(t\) \(\leq\) \(10^3\)) và mỗi test bao gồm 4 dòng:

• Dòng thứ nhất ghi 1 số nguyên \(n\) là số lượng phần tử của \(a\) và \(b\) (\(1 \leq n \leq 10\))
• Dòng thứ 2 bao gồm \(n\) số \(a_1\), \(a_2\), \(a_3\),... \(a_{n-1}\), \(a_n\) (\(0 \leq a[i] \leq 10^9\))
• Dòng thứ 3 bao gồm \(n\) số \(b_1\), \(b_2\), \(b_3\),... \(b_{n-1}\), \(b_n\) (\(0 \leq b[i] \leq 10^9\))
• Dòng thứ 4 ghi 1 số nguyên \(k\) (\(1 \leq k \leq 10^9\))

Output

Gồm \(t\) dòng, mỗi dòng là số nguyên \(c_k\) cần tìm mod cho \(10^9\)

Ví dụ

Input

2
3
1 2 3
4 5 6 
3
3
17082004 27092004 12032004
01052004 24022004 09092004
10

Output

3
119266304

Giải thích: tự hiểu chứ giải thích gì

yenthanh132 vừa trúng vé số, anh ta định mua một hòn đảo để xây nhà nghỉ mát. Thế là anh ta để ý ngay đến vương quốc đảo dừa trù phú của Pirate vĩ đại. Sau cuộc nội chiến dừa và vụ "tam phân thiên hạ" lộn xộn vừa rồi thì hiện vương quốc dừa đã được bình yên với sự cai trị của vị vua mới - Pirakute (Xem bài [VOJ]VMAOCE để biết thêm chi tiết). Do rất yêu quê hương đảo nước của mình nên Pirakute đã một mực không chịu bán bất cứ hòn đảo nào cho yenthanh132 , tuy nhiên nhờ sự đàm phán lâu dài cùng với mức giá kết xù của yenthanh132 đưa ra để mua đảo nên Pirakute sau khi suy nghĩ một thời gian đã đưa ra quyết định. Pirakute sẽ đồng ý bán cho yenthanh132 một hòn đảo với điều kiện anh ta phải tính được số hòn đảo hiện có trong vương quốc dừa.

Do sau một thời gian dài nội chiến nhiều thông tin đã bị mất, không ai thống kê lại xem hiện thời vương quốc dừa có tổng cộng bao nhiêu đảo. Thay vào đó chỉ còn lại một tài liệu cổ nói về lịch sử của vương quốc dừa từ thuở khai thiên lập địa. Tài liệu nói rằng từ thời xa xưa, cụ tổ Pirate đã xây dựng từng hòn đảo bằng cách chở dừa đến và chất thành đống ở giữa biển, các trái dừa này sẽ mọc ra những cây dừa và thế là một hòn đảo dừa được tạo ra. Lịch sử nói rằng \(K\) năm đầu tiên là thời kì khó khăn nhất của vương quốc dừa. Do có một số hòn đảo chất lượng không tốt nên bị mất đi và việc Pirate kiên trì tạo thêm các hòn đảo mới nên số lượng các hòn đảo qua \(K\) năm đầu tiên lên xuống thất thường nhưng luôn có ít nhất một đảo. Số lượng hòn đảo trong \(K\) năm đầu được lịch sử ghi lại trong dãy số \(a_1, a_2, ..., a_K\). Sau \(K\) năm đó, tức là kể từ năm \(K+1\), các cây dừa trên hòn đảo đã trưởng thành và cho trái, các trái dừa rớt xuống biển và tự động tạo nên các hòn đảo dừa mới một cách tự nhiên. Số lượng đảo dừa từ đó tăng một cách chống mặt và vương quốc dừa trở thành một đại cường quốc. Lịch sử cũng nói lại rằng số lượng đảo dừa trong năm thứ \(i\) sẽ bằng tích số lượng đảo dừa của \(K\) năm trước. Tức là số lượng đảo dừa của vương quốc trong năm \(i\) bằng \(a_i=a_{i−1}×a_{i−2}×⋯×a_{i−K}\). Mặc dù vương quốc đã trải qua nhiều thăng trầm, chiến tranh liên miên nhưng số lượng đảo dừa qua từng năm vẫn tăng đều theo công thức đó.

Thế là có đủ thông tin để yenthanh132 có thể tính được số lượng đảo dừa của vương quốc dừa. Nhưng tính tới thời điểm hiện tại đã là năm tồn tại thứ \(N\) của vương quốc và \(N\) là một số rất lớn nên không ai có thể tính được. yenthanh132 định dùng siêu máy tính mà anh ta đã mua hôm nọ ( TNHTEST ) nhưng khổ nỗi vương quốc dừa dùng điện năng lượng mặt trời nên không có đủ điện để chạy siêu máy tính được. Thế là giờ chỉ còn mỗi cái Laptop Pentium 3 800Mhz là có thể dùng được. Bạn là một nhà lập trình viên siêu hạng, hãy giúp yenthanh132 và chứng tỏ rằng Laptop cùi tới mấy mà biết sử dụng thì cũng có thể làm nên chuyện 🙂

Yêu cầu

• Cho số \(N, K\) và dãy số \(a_1, a_2, ..., a_K\) - số đảo dừa trong vương quốc qua \(K\) năm đầu
• Với \(i>K\) ta có \(a_i=a_{i−1}×a_{i−2}×⋯×a_{i−K}\);
• Tính \(a_N\), do số lượng hòn đảo rất lớn nên yenthanh132 chỉ yêu cầu bạn tính phần dư của kết quả khi chia cho số \(1000000007\) \((10^9+7)\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, K (1 \le N \le 10^9,1 \le K \le 50,K<N)\).
• Dòng thứ hai ghi \(K\) số nguyên dương, số thứ \(i\) của dãy số là \(a_i (1 \le a_i \le 10^9)\)

Output

• Ghi ra kết quả theo modulo \(1000000007\) \((10^9 + 7)\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 100000\).
• Subtask \(2\) (\(70\%\) số điểm): \(N \le 10^9\).

Example

7 3
1 2 3

139968

Turing hiện đang làm việc để crack các máy bí ẩn. Nhưng ông thấy rằng có hai hàm toán học là \(f(n)\) và \(g(n)\) được sử dụng để mã hóa tin nhắn của người Đức. Ông muốn thử nghiệm khám phá của mình để bắt chước cách mã hóa của máy tính.

Các hàm được định nghĩa là:

• \(g (n + 1) = 4 \times g (n) + f (n + 1) + c\)
• \(f (n + 2) = 3 \times f (n + 1) + 2 * f (n)\)

Dữ liệu ban đầu:

• \(f (0) = 1;\)
• \(f (1) = 1;\)
• \(g (-1) = 1;\)
• \(g (0) = 1;\)
• \(c = 2;\)

Yêu cầu: Cho số nguyên \(n\), cần phải tìm giá trị \(g(n)\mod 10^9+7\).

Input

• Dòng đầu tiên ghi số lượng các trường hợp thử nghiệm \(T\),
• \(T\) dòng tiếp theo mỗi dòng ghi một giá trị của \(n\).

Output

• Với mỗi test \(T\), xuất ra giá trị của \(g(n)\).

Example

5
1
2
3
6
1000

7
35
159
12835
566998663

Dù thông minh, đẹp trai, học giỏi nhưng vẫn không thoát khỏi kiếp FA vì chỉ có 8cm và lười tắm, Khánh 3508 lại buồn bã trở về vnoi code lại từ đầu. Trong một ngày chán như con gián, Khánh 3508 nhổ trộm bông hướng dương nhà hàng xóm và ngồi … đếm cánh hoa. Mỗi lần một cánh hoa rụng xuống là câu nói “Tắm”, “Không tắm” lại vang lên. Đã ba năm trôi qua Khánh 3508 vẫn chỉ ngồi đếm lá và chưa tắm rồi đột nhiên anh ta đứng lên và chạy về máy tính: “Đúng rồi số ngẫu nhiên!”. Hóa ra Khánh 3508 đã nghĩ ra cách làm mới mà không phải nhổ trộm hoa + ngồi đếm số cánh hoa. Chúng ta biết rằng số ngẫu nhiên được sinh ra bởi bộ ba số \(a, b, m\) theo quy tắc:

• Số thứ nhất là \(x_1 =b \mod m\)
• Số thứ \(k\) là \((a*x_{k-1} +b) \mod m\) với \(k>1\)

Khánh 3508 sẽ lấy số \(x_k\) để so với lịch xem nó có phải ngày đẹp hay không để quyết định tắm rửa. Tuy nhiên do thích chơi trội Khánh 3508 đã để \(a, b, m, k\) rất lớn khiến máy tính bị đơ. Bạn hãy giúp Khánh tính \(x_k\) thật nhanh để cậu ta có thể tắm.

Input

• Dòng 1: Số nguyên \(T (1\le T\le 10)\) là số lượng test
• \(T\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(a, b, m, k (1\le a, b, m, k\le 10^{15})\)

Output

• Gồm \(T\) dòng, mỗi dòng in ra số \(x_k\) tương ứng.

Example

3
1 1 1 1
2 5 100 6
1 8 777 6

0
15
48

Nguyên rất thích trò chơi xếp tháp. Tòa tháp của Nguyên bao gồm những khối lăng trụ đứng có đáy hình vuông và chiều cao bằng 1. Nguyên sẽ xếp các khối lăng trụ chồng lên nhau để tạo thành một tòa tháp cao.

Mới đây trong lớp học toán, Nguyên được cô giáo dạy về cách tính thể tích các hình khối đơn giản. Nguyên thích thú với kiến thức mới học được và cậu ta muốn tính thể tích tòa tháp của mình.

Tháp của Nguyên bao gồm \(N\) khối lăng trụ đứng chiều cao 1 và có đáy hình vuông và độ dài cạnh đáy từ trên xuống dưới theo thứ tự là \(A_1, A_­­­2, ... A_­­N.\) Dãy \(A\) được tạo như sau:

• \(A_1 = 1.\)
• \(A_2\) sẽ là một số dương tùy ý mà Nguyên chọn trong mỗi lần chơi để tránh nhàm chán.
• \(A_i (i > 2)\) bằng \(2 × A_2 × A_{i-1}–A_{i-2}\)

Nguyên biết rõ thể tích hình một hình lăng trụ sẽ bằng chiều cao nhân với diện tích đáy nhưng vì ngại tính toán, Nguyên muốn nhờ bạn viết một chương trình giúp cậu ta. Kết quả có thể rất lớn vì vậy bạn chỉ cần ghi ra theo \(\mod M\) với \(M\) là một số nguyên dương cho trước.

Input

• Dòng 1: Ghi số nguyên dương \(K \le 10\) là số bộ dữ liệu.
• \(K\) dòng tiếp: Mỗi dòng ghi 3 số nguyên \(A_2, N, M\) tương ứng với một bộ dữ liệu. (\(1 \le A_2, M \le 10^9, 2\le N \le 10^9\))

Output

• Với mỗi bộ test ghi ra một số duy nhất là kết quả tương ứng trên một dòng.

Example

2
1 10 1000
2 3 100 

10
54

Cho dãy (\(a_i\)) các số tự nhiên được định như sau:

• \(a_i = b_i\) (với \(i \le k\))
• \(a_i = c_1a_{i-1} + c_2a_{i-2} + ... + c_ka_{i-k}\) (với \(i > k\))

Với \(b_i\) và \(c_i\) là các số tự nhiên cho trước (\(1\le i\le k\)). Hãy tính \(a_n \mod 10^9\), với \(n\) cho trước.

Input

• Dòng đầu tiên chứa số \(c\) là số lượng test (\(1\le c\le 1000\)). Mỗi test chứa 4 dòng:
• Dòng 1: chứa số \(k\), là số phần tử của dãy \(c\) và \(b\) (\(1 \le k \le 10\))
• Dòng 2: chứa các số \(b_1,...,b_k\) với \(0 \le b_i \le 10^9\), mỗi số cách nhau một dấu cách.
• Dòng 3: chứa các số \(c_1,...,c_k\) với \(0 \le c_i \le 10^9\), mỗi số cách nhau một dấu cách.
• Dòng 4: chứa số \(n\) (\(0 \le n \le 10^9\))

Output

• Gồm \(c\) dòng, mỗi dòng là kết quả của một test, ghi giá trị: \(a_n \mod 10^9\)

Example

3 
3 
5 8 2 
32 54 6 
2 
3 
1 2 3 
4 5 6 
6 
3 
24 354 6 
56 57 465 
98765432

8 
714 
257599514

Năm 1202, Leonardo Fibonacci, nhà toán học người Ý, tình cờ phát hiện ra tỉ lệ bàng 0.618 được tiệm cận bằng thương của hai số liên tiếp trong một loại dãy số vô hạn được một số nhà toán học ẤN ĐỘ xét đến từ năm 1150. Sau đó dãy số này được đặt tên là dãy số \(Fibonacci\) {\(F_i: i=1, 2, ...\)}, trong đó \(F_1=F_2=1\) và mỗi số tiếp theo trong dãy được tính bằng tổng của hai số ngay trước nó. Đây là 10 số đầu tiên của dãy số \(Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 35\). Người ta đã phám phá ra mối liên hệ chặt chẽ của số \(Fibonacci\) và tỉ lệ vàng với sự phát triển trong tự nhiên (cánh hoa, cành cây, vân gỗ), trong vũ trụ (hình xoáy trôn ốc dải ngân hà, khoảng cách giữa các hành tinh), hay sự cân đối của cơ thể con người. Đặc biệt số \(Fibonacci\) được ứng dụng mạnh mẽ trong kiến trúc (Kim tự tháp Ai Cập, tháp Eiffel), trong mỹ thuật (các bức tranh của Leonardo da Vinci), trong âm nhạc (các bản giao hưởng của Mozart) và trong nhiều lĩnh vực khoa học kĩ thuật.

Trong toán học, dãy \(Fibonacci\) là một đối tượng tổ hợp quan trọng có nhiều tính chất đẹp. có nhiều phương pháp hiệu quả liệt kê và tính các số \(Fibonacci\) như phương pháp lặp hay phương pháp nhân ma trận.

Sau khi được học về dãy số \(Fibonacci\), Sơn rất muốn phát hiện thêm những tính chất của dãy số này. Vì thế Sơn đặt ra bài toán sau đây: Hỏi rằng có thể tìm được một tập con các số trong \(n\) số \(Fibonacci\) liên tiếp bắt đầu từ số thứ \(i\), sao cho tổng của chúng chia hết cho một số nguyên dương \(k (k\le n)\) cho trước hay không? Nhắc lại, một tập con \(q\) số của một dãy \(n\) số là một cách chọn ra \(q\) số bất kỳ trong \(n\) số của dãy đó, mỗi số được chọn không quá một lần.

Yêu cầu: Hãy giúp Sơn giải quyết bài toán đặt ra.

Dữ liệu

• Dòng thứ nhất ghi số nguyên dương \(T (T\le 10)\) là số lượng bộ dữ liệu.
• Mỗi dòng trong \(T\) dòng tiếp theo chứa ba số nguyên dương \(n, i\) và \(k\) là thông tin của một bộ dữ liệu.

Kết quả

• Ghi ra \(T\) dòng tương ứng với kết quả của \(T\) bộ dữ liệu đầu vào, mỗi dòng có cấu trúc như sau: Đầu tiên ghi số nguyên \(q\) là số lượng các số trong tập con tìm được, tiếp đến ghi \(q\) số nguyên là các số thứ tự trong dãy \(Fibonacci\) của \(q\) số trong tập con tìm được. Nếu không tìm được tập con thỏa mãn điều kiện đặt ra thì ghi ra một số 0.
• Nếu có nhiều cách chọn thì chỉ cần đưa ra một cách chọn bất kỳ (chưa viết checker).

Input

1
10 3 9

Output

2 5 7

Giải thích: Trong ví dụ trên một tập con thỏa mãn điều kiện đặt ra là tập gồm 2 số \(F5=5, F7=13\) với tổng bằng \(18\).

Ràng buộc

• Có 20% số lượng test thỏa mãn điều kiện: \(n≤20, i≤10^6\)
• Có 20% số lượng test thỏa mãn điều kiện: \(n≤10^3 , i≤10^6\)
• Có 20% số lượng test thỏa mãn điều kiện: \(n≤10^6, i≤10^6\)
• Có 10% số lượng test thỏa mãn điều kiện: \(n≤20, i≤10^{15}\)
• Có 10% số lượng test thỏa mãn điều kiện: \(n≤10^3, i≤10^{15}\)
• Có 20% số lượng test còn lại thỏa mãn điều kiện: \(n≤10^6, i≤10^{15}\)

Nguồn: VOI 2017

Okabe thích đi bộ nhưng biết rằng gián điệp có thể ở bất cứ đâu; đó chính là lý do tại sao anh ấy muốn biết có bao nhiêu cách khác nhau mà anh ta có thể đi trong thành phố của mình một cách an toàn. Thành phố của Okabe có thể được biểu diễn bởi các điểm (\(x, y\)) sao cho \(x\) và \(y\) không âm. Okabe bắt đầu đi tại điểm gốc (điểm (\(0, 0\))) và cần đi đến điểm (\(k, 0\)). Nếu Okabe đang ở điểm (\(x, y\)), trong một bước anh ta có thể đi đến (\(x + 1, y + 1\)), (\(x + 1, y\)), hoặc (\(x + 1, y - 1\)).

Ngoài ra, có \(n\) đoạn đường ngang, đoạn thứ \(i\) từ \(x=a_i\) đến \(x=b_i\) và ở tung độ \(y=c_i\). Luôn đảm bảo rằng \(a_1=0, a_n \le k \le b_n\) và \(a_i=b_{i-1}\) với \(2 \le i \le n\). Đoạn đường thứ \(i\) buộc Okabe phải đi với giá trị \(y\) trong phạm vi \(0 \le y \le c_i\), còn giá trị \(x\) phải thoả mãn \(a_i \le  x \le  b_i\), nếu không anh ta có thể bị theo dõi. Điều này cũng có nghĩa là anh ta bắt buộc phải ở dưới hai đoạn đường khi một đoạn đường kết thúc và một đoạn khác bắt đầu.

Okabe muốn biết có bao nhiêu cách đi an toàn từ điểm đầu (\(0,0\)) tới điểm (\(k,0\)), kết quả \(\mod 10^9 + 7\).

Input

\(Input\)

• Dòng đầu chứa hai số nguyên \(n\) và \(k (1 \le  n \le  100, 1 \le  k \le  10^{18})\) là số đoạn đường ngang và tọa độ \(x\) của điểm kết thúc.
• \(N\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(a_i, b_i\) và \(c_i\) (\(0 \le  a_i < b_i \le  10^{18}, 0 \le  c_i \le  15\)) tương ứng là hoành độ đầu mút trái, hoành độ đầu mút phải, tung độ của một đoạn đường ngang.
• Dữ liệu luôn đảm bảo rằng \(a_1 = 0, a_n \le  k \le  b_n\), và \(a_i = b_i - 1\) với \(2 \le  i \le  n\).

Output

• Ghi số lượng cách đi thỏa mãn điều kiện, kết quả \(\mod 10^9 + 7\).

"

Sau một ngày mệt nhọc đón các đoàn về tham dự Trại hè tin học 2017, thầy Minh vô cùng mệt mỏi ngủ ngay khi học sinh về hết phòng. Trong giấc mơ, thầy Minh mơ đang vẽ một cây vô hạn, mỗi nút có đúng \(n\) nút con, khoảng cách từ nút cha tới các nút con của nó theo thứ tự từ trái sang phải là \(d_1, d_2, … , d_n\). Thầy Minh đang có một số \(k\) và rất muốn biết có bao nhiêu đỉnh trên cây mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\).

Dữ liệu

• Dòng đầu chứa hai số nguyên dương \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(d_1, d_2, … , d_n (d_i ≤ 100)\)

Kết quả

• Số lượng đỉnh mà khoảng cách từ đỉnh đó tới gốc không vượt quá \(k\). Đưa ra theo số dư cho \(10^9 + 7\).

Input

3 3 
1 2 3

Output

8

Giới hạn

• 50% test có \(k ≤ 10000, n ≤ 100\)
• 50% test có \(1000 < k ≤ 10^{18}, n≤ 100000\)

Nguồn: CĐ DHBB

Ma trận

Phép cộng hai ma trận có cùng kích thước \(m\text{x}n\), ma trận tổng \(C=A+B\) có kích thước \(m\text{x}n\), phần tử đứng ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

\(c_{i,j}=a_{i,j}+b_{i,j}\)

Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận bên phải. Nếu ma trận \(A\) có kích thước \(m\text{ x }n\) và ma trận \(B\) có kích thước \(n\text{ x }p\), thì ma trận \(C=A\text{ x }B\) có kích thước \(m\text{ x }p\), phần tử ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

\(c_{i,j}=a_{i,1}b_{1,j}+a_{i,2}b_{2,j}+...+a_{i,n}b_{n,j}\)

Phép nhân ma trận có các tính chất sau:

• Tính chất kết hợp: \((A\text{ x }B)\text{ x }C=A\text{ x }(B\text{ x }C);\)

• Tính chất phân phối: \((A+B)\text{ x }C=A\text{ x }C+B\text{ x }C; C\text{ x }(A+B)=C\text{ x }A+C\text{ x }B\)

Cần chú ý rằng phép nhân ma trận không giao hoán

Ví dụ,

\(\begin{pmatrix}0&1\\1&1\end{pmatrix};A^2=\begin{pmatrix}1&1\\1&2\end{pmatrix};A^3=\begin{pmatrix}1&2\\2&3\end{pmatrix};...\)

\(A+A^2+A^3=\begin{pmatrix}2&4\\4&6\end{pmatrix}\)

Yêu cầu: Cho ma trận \(A\) kích thước \(n\text{x}n\) và số nguyên dương \(k\), hãy tính \(B=A+A^2+...+A^{k}\)

Input:

• Dòng đầu chứa hai số nguyên \(n,k(n\le 20);\)

• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyêm.

Output:

• Gồm \(n\) dòng, mỗi dòng \(n\) số mô tả ma trận \(B\), vì giá trị mỗi phần tử của ma trận \(B\) có thể rất lớn, do đó chỉ cần đưa ra chữ số cuối cùng của từng phần tử của ma trận \(B\)

Ví dụ:

Input:

2 3
0 1
1 1

Output:

2 4
4 6

Subtask:

• Subtask 1: \(k\le 10^2\)

• Subtask 2: \(k\le 10^9\)

http://lequydon.ntucoder.net/ckfinder/userfiles/files/matrix.pdf

Nguồn: 3d20

Cho lưới \(3 × N\) điểm. Mỗi điểm có tối đa 8 điểm xung quanh.

Người ta nối các điểm của lưới tạo thành một đường gấp khúc khép kín với các tính chất sau:

Đường gấp khúc chứa tất cả \(3 × N\) điểm của lưới.
Chỉ các đỉnh kề nhau mới được nối với nhau
Đường gấp khúc không tự cắt

Figure 2: Ví dụ 2 cách nối với \(N = 6\).

Hãy viết chương trình tính số cách nối thỏa mã các điều kiện trên. Chú ý in ra kết quả theo mô đun \(1,000,000,000\).

Input

• Dòng duy nhất chứa số nguyên \(N (N \le 1,000,000,000)\).

Output

• Gồm một dòng duy nhất là số cách nối theo mô đun \(1,000,000,000\).

Example

3

8

4

40

Trên một bàn cờ vua có chiều dài và chiều rộng vô hạn, xuất hiện \(n\) con vua: \(K = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) \}\).

Nếu các bạn chưa biết chơi cờ, con vua mỗi bước có thể đi sang 8 ô kề nó, tính cả đi chéo.

Bạn có thêm một quân vua TỐI CAO đứng tại vị trí \((x, y)\), có sức mạnh của là tổng của từng số bước đi tối thiểu để con vua tối cao này có thể đi tới từng con vua khác.

Một cách quy củ, gọi \(d_i\) là số bước đi tối thiểu để vua tối cao có thể đi tới vua thứ \(i\), thì sức mạnh của vua tối cao là \(\sum_{i=1}^{n} d_i\).

\(n\) con vua trên không muốn vị tối cao này lộng hành, nên muốn sức mạnh của nó nhỏ nhất có thể. Bạn hãy tìm lượng sức mạnh tối thiểu này là bao nhiêu, và số lượng vị trí để đạt lượng tối thiểu này nhé.

Input

• Dòng đầu tiên gồm số \(n\)
• \(n\) dòng sau lần lượt gồm \(x_i, y_i\) là vị trí của con vua thứ \(i\).

Output

• Gồm 2 số, là sức mạnh tối thiểu của con vua tối cao, và số vị trí đặt con vua này để đạt lượng sức mạnh tối thiểu.

Example

3
0 0
1 3
4 1

5 1

Trên một bàn cờ vua có chiều dài và chiều rộng vô hạn, xuất hiện \(n\) con vua đánh số từ \(1\) tới \(n\): \(K = \{(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) \}\).

Nếu các bạn chưa biết chơi cờ, con vua mỗi bước có thể đi sang 8 ô kề nó, tính cả đi chéo.

\(n\) con vua này bầu ra \(1\) vị vua tối cao đứng tại vị trí \((x_i, y_i)\), có sức mạnh của là tổng của từng số bước đi tối thiểu để con vua tối cao này có thể đi tới mỗi con vua trong số \(n-1\) con còn lại.

Một cách quy củ, gọi \(d(i, j)\) là số bước đi tối thiểu để vua thứ \(i\) có thể đi tới vua thứ \(j\) (mặc định \(d(i, i) = 0\)). Nếu vua tối cao là vua thứ \(x\) thì sức mạnh của nó là \(\sum_{i=1}^{n} d(x, i)\).

\(n - 1\) con vua còn lại không muốn bầu ra vị tối cao lộng hành, nên muốn sức mạnh của nó nhỏ nhất có thể. Bạn hãy giúp họ chọn ra vị vua tối cao anh minh yếu ớt này, và lượng sức mạnh tối thiểu nhé.

Input

• Dòng đầu tiên gồm số \(n\)
• \(n\) dòng sau lần lượt gồm \(x_i, y_i\) là vị trí của con vua thứ \(i\).

Output

• Dòng đầu tiên gồm 2 số, là sức mạnh tối thiểu của con vua tối cao, và số con vua thỏa mãn sức mạnh có thể được bầu.
• Dòng sau in ra chỉ số các con vua thỏa mãn.

Example

4 
0 0 
1 3 
4 1 
3 -2

10 2
1 3

Cho \(n \leq 3*10^5\) điểm trên mặt phẳng tọa độ Oxy. Bạn cần tính khoảng cách lớn nhất giữa 2 điểm bất kì.

Biết công thức tính khoảng cách Manhattan giữa 2 điểm \(A\) và \(B\) là \(|x_{A} - x_{B}| + |y_{A} - y_{B}|\).

Input

Dòng đầu tiên chứa một số nguyên \(n\).

Trong \(n\) dòng tiếp theo, mỗi dòng chứa 2 số \(x_i, y_i\) là tọa độ của điểm thứ \(i\).

Mọi điểm được cho đều có tọa độ nguyên và \(|x|,|y| \leq 10^9\).

Output

Một số nguyên duy nhất là kết quả của bài toán.

Example

3
1 -2
3 7
-6 4 

13

Cho \(n \leq 10^5\) điểm trên mặt phẳng tọa độ Oxy. Bạn cần tính khoảng cách bé nhất giữa 2 điểm bất kì.

Biết công thức tính khoảng cách Manhattan giữa 2 điểm \(A\) và \(B\) là \(|x_{A} - x_{B}| + |y_{A} - y_{B}|\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\).

• Trong \(n\) dòng tiếp theo, mỗi dòng chứa 2 số \(x_i, y_i\) là tọa độ của điểm thứ \(i\).

• Mọi điểm được cho đều có tọa độ nguyên và \(|x|,|y| \leq 10^9\).

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Example

5
3 -2
1 4
-6 7
10 8
-5 0

8

Cuộc chiến tranh chống đế quốc Mĩ là một trong những cuộc chiến tranh tàn khốc và đẫm máu nhất trong lịch sử của Vê Be(Wb). Mặc dù bây giờ hòa bình đã trở lại, nhưng những vết tích của chiến tranh vẫn hằng sâu trong tâm trí của mỗi người lính.

BeTapDi - Tổng tham mưu trưởng quân đội nhân dân Vê Be(Wb) đã bày tỏ những cảm xúc kinh hoàng khi nhớ lại cuộc chiến tranh khốc liệt này. Ông nói: "Hồi đó, lúc còn đánh ở Đà Nẵng, ngày nào tui cũng nghe tiếng máy bay với bom nổ rầm trời, mấy thằng Mĩ nó lái \(R52\) thả bom như mưa, tôi ở dưới hầm mà sợ còn hơn trên mặt trận vì không biết khi nào mình đi thỉnh kinh. Mấy đứa bạn tôi thấy quá sợ khi phải trải qua những ngày như thế nên bọn nó làm liều, xông ra mặt trận quyết tử nên quyên sinh luôn. Còn mỗi tôi với ông đại úy, 2 người chả biết làm gì đành trốn dưới hầm mấy ngày liền. Tự dưng bọn Mĩ nó không thả bom nữa, cũng chả thấy tên lính hay chiếc \(R52\) nào nên bọn tôi bèn đi lên thì thấy cái cảnh hoang tàn hệt như lúc tôi nấu ăn ở nhà vậy. À mà thực ra mấy chiếc đó là \(B52\), nhưng vì bom nó nổ ra cái \(hình\) \(thoi(rhombus)\) nên tui đặt là \(R52\) luôn cho nó dễ hiểu."

Ông nói thêm: "Thấy cái cảnh đó lòng tôi đau như cắt. Ông đại úy cũng vậy, nhìn mà thấy bủh bủh, lmao. Ông ấy lệnh cho tôi đi đo lường thiệt hại của Đà Nẵng (Measure of Damage). Sau khi nghe ông đại úy nói Đà Nẵng diện tích khổng lồ tận \(N * M\) thì tui cũng choáng luôn. Hên là trước khi đi lính, tui có học 1 khóa C++ với lại ở đó cũng có cái laptop khá xịn nên tui nhảy vô code luôn cái chương trình đo lường. Mà tui lại mắc phải cái vấn đề là không có số liệu, chỉ thấy cái cảnh hoang tàn đó thì làm sao đo được. Thế là tui hỏi ông đại úy, ổng nói là lúc trong hầm chán quá, ổng nghe tiếng bom nổ rồi ghi lại nơi tất cả quả bom rơi và độ lớn của vụ nổ nhờ tiếng nổ. Với độ lớn vụ nổ là \(power\) và vụ nổ xảy ra tại ô \((x, y)\) thì những ô có khoảng cách Manhattan tới ô \((x, y) <= power\) sẽ bị ảnh hưởng. Tui thề lúc đó tui cũng không hiểu ổng có phải thần hay là tiên nữa mà nói chung là ảo diệu thật sự. Nhưng mà có nhiều chỗ bom rơi nhiều quá nên ông đại úy muốn đo lường thiệt hại ở nơi đó vào thời điểm đó nên cuối cùng cái danh sách của ổng cũng loạn luôn. Giờ tui vẫn còn giữ cái danh sách ở đây nên tui muốn xem thử các bạn đang đọc cái đề này giải thử xem trình học sinh ngày nay thế nào =))"

Input

Dòng đầu tiên chứa bốn số \(Task,\) \(N,\) \(M,\) \(Q\) lần lượt là số thứ tự subtask, chiều rộng, chiều dài của Đà Nẵng và số lượng truy vấn của danh sách.

\((1 \le Task \le 3),\) \((1 \le N, M \le 10^9),\) \((1 \le Q \le 10^5)\).

\(Q\) dòng tiếp theo, dòng thứ \(i\) chứa \(t[i]\) \((1 \le t[i] \le 2)\) là loại truy vấn của truy vấn thứ \(i\).

• Với \(t[i] = 1\), dòng đó sẽ chứa thêm 3 số \(x[i],\) \(y[i]\) và \(pow[i]\) lần lượt là vị trí xảy ra vụ nổ và độ lớn vụ nổ.
• Với \(t[i] = 2\), dòng đó sẽ chứa thêm 2 số \(x[i],\) \(y[i]\) tức là BeTapDi muốn bạn trả lời xem rằng ô \((x[i], y[i])\) đã bị ảnh hưởng bởi bao nhiêu vụ nổ.

\((1 \le x[i] \le N),\) \((1 \le y[i] \le M),\) \((1 \le pow[i] \le max(N, M))\)

Output

Với mỗi truy vấn loại 2, in ra một số trên một dòng là số vụ nổ đã ảnh hướng tới ô ở truy vấn đấy.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \((1 \le N, M \le 200),\) \((1 \le Q \le 100)\)
• Subtask \(2\) (\(30\%\) số điểm): \((1 \le N, M \le 1000),\) \((1 \le Q \le 1000)\)
• Subtask \(3\) (\(40\%\) số điểm): \((1 \le N, M \le 10^9),\) \((1 \le Q \le 10^5)\)

Example

1 8 11 6
1 5 8 3
2 5 11
1 3 11 2
2 3 9
1 5 11 0
2 5 11

1
2
3