Vào một buổi học toán nọ, thầy giáo ghi lên bảng một bài toán: Cho số ~n~. Có thể biến đổi ~n~ bằng cách lặp lại nhiều lần thao tác sau:

• Tăng ~n~ thêm một đơn vị. Sau khi tăng, nếu ~n~ chia hết cho ~10~ thì chia ~n~ cho ~10~.

Hãy đếm xem có bao nhiêu giá trị ~n~ có thể được tạo ra từ cách biến đổi trên (số lần biến đổi có thể là ~0~)

Thầy giáo cho phép học sinh nào giải được thì sẽ được thầy thưởng một cốc milo dầm, nghe thấy thế, ~taph~ - một câu học sinh vốn ham milo hơn ham học, đặc biệt là loại milo dầm, vô cùng thích thú. Khổ nỗi là cậu lại không có máy tính ở đây, bạn hãy giúp cậu ấy giải bài toán này nhé!

Input

• Một dòng duy nhất chứa số nguyên ~n~ ~(1 \le n \le 10^9)~

Output

• In ra một dòng duy nhất, là số các số có thể tạo ra qua việc biến đổi ~n~.

Sample Input 1

2

Sample Output 1

9

Sample Input 2

177013

Sample Output 2

37

Note

• Ở test mẫu #1, từ số ~2~ ta có thể biến đổi thành các số ~2, 3, 4, 5, 6, 7, 8, 9, 1~.

~Minh~ là một cậu bé khó tính. Cậu có sở thích sưu tầm những mảng số khác nhau.

Dạo gần đây, cậu ấy vừa nhặt được một mảng ~A~ gồm ~n~ số nguyên.

Minh không hài lòng với mảng ~A~ hiện tại. Cậu ấy sẽ tạo ra mảng ~B~ mới từ ~A~ bằng cách sau:

• Đầu tiên, mảng ~B~ là mảng rỗng.
• Lần lượt đi từ phần tử đầu tiên ~(A_1)~ cho đến phần tử cuối cùng ~(A_n)~. Tại lượt thứ ~i~, Minh sẽ thêm ~A_i~ vào đầu hoặc cuối của mảng ~B~.

Sau khi thực hiện thao tác trên, Minh sẽ được mảng ~B~ mới gồm ~n~ phần tử.

Minh muốn tạo mảng ~B~ sao cho độ dài của dãy con tăng ngặt tìm được trên ~B~ là lớn nhất. Hãy giúp Minh đạt được điều này.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(|A_i| \le 10^9)~.

Output

• Một số duy nhất là độ dài dãy con tăng ngặt dài nhất tìm được sau khi thay đổi dãy ~A~ bằng thao tác trên.

Sample Input

6
4 5 5 6 3 7

Sample Output

5

Subtask

• ~40~% số test với ~1 \le n \le 20~.
• ~30~% số test tiếp theo với ~1 \le n \le 1000~.
• ~30~% số test còn lại không có ràng buộc gì thêm.

Note

Ở test mẫu đầu tiên, lần lượt thực hiện như sau:

• Thêm số ~4~ vào mảng, mảng ~B~ trở thành ~[4]~.
• Thêm số ~5~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5]~.
• Thêm số ~5~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5, 5]~.
• Thêm số ~6~ vào cuối mảng, mảng ~B~ trở thành ~[4, 5, 5, 6]~.
• Thêm số ~3~ vào đầu mảng, mảng ~B~ trở thành ~[3, 4, 5, 5, 6]~.
• Thêm số ~7~ vào cuối mảng, mảng ~B~ trở thành ~[3, 4, 5, 5, 6, 7]~.

Khi đó, dãy con tăng ngặt dài nhất là ~[3, 4, 5, 6, 7]~, với độ dài là ~5~.

Ở xưởng xí nghiệp Bedao, có ~k~ người thợ và có ~n~ tấm bảng cần tô được đặt cạnh nhau, tấm bảng thứ ~i~ tô tốn mất ~a_i~ đơn vị thời gian. Tại một thời điểm, mỗi người thợ chỉ được tô một tấm bảng.

Để hoàn thành công việc này trong thời gian nhanh nhất có thể, ~k~ người thợ đã thống nhất chia ~n~ tấm bảng thành ~k~ phần phân biệt, mỗi phần gồm một hoặc một số tấm bảng bất kì trong ~n~ tấm bảng.

Dưới vai trò là một chủ xưởng xí nghiệp, bạn cần phải chia ~n~ tấm bảng thành ~k~ phần sao cho thời gian hoàn thành công việc là sớm nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~( 1 \leq k \leq n \leq 12 )~
• ~n~ dòng tiếp theo là các số ~a_i~ là thời gian để tô tấm bảng thứ ~i~ ( ~1 \leq a_i \leq 10^3~ )

Output

• Một số nguyên là thời gian sớm nhất để hoàn thành công việc yêu cầu

Sample Input

4 3
1 
5 
3 
5

Sample Output

5

Note

Ta có thể chia ~4~ tấm bảng thành ~3~ phần như sau: ~{[1,3],[5],[5]}~ và có thời gian hoàn thành công việc là ~5~, cũng là thời gian hoàn thành sớm nhất

~Neko~ có ~1~ bàn cờ kích cỡ ~2*10^5 \times 2*10^5~ ô, trên bàn cờ được đặt sẵn ~n~ quân xe sao cho trên mỗi hàng và mỗi cột không có quá ~2~ quân xe. Cậu ta thấy rằng một hàng hoặc một cột được gọi là bị "thống trị" nếu như trên đó có duy nhất ~1~ quân xe. Biết rằng được phép chọn tùy ý một số các quân xe và bỏ chúng khỏi bàn cờ, bạn hãy giúp cậu ấy đếm số trạng thái bàn cờ sao cho không có hàng hoặc cột bị thống trị.

Input

• Dòng đầu tiên chứa số nguyên ~n~ là số quân xe ~( 1 \leq n \leq 2*10^5 )~
• ~n~ dòng tiếp theo, mỗi dòng gồm ~1~ cặp số nguyên ~(x, y)~ lần lượt là tọa độ hàng và cột của một quân xe, đảm bảo không có 2 quân xe ở cùng vị trí.

Output

• Một số duy nhất là số trạng thái bàn cờ thỏa mãn yêu cầu, do đáp án có thể rất lớn nên in ra kết quả với phần dư của phép chia ~10^9+7~

Sample Input

5
1 1
5 5
1 5
5 1
3 3

Sample Output

2

Subtask

• ~20~% số test với ~1 \le n \le 10~.
• ~80~% số test tiếp theo không ràng buộc gì thêm.

Note

Bỏ quân xe ở tọa độ ~(3, 3)~ hoặc bỏ toàn bộ các quân xe.

Hôm nay là một ngày rất đặc biệt - sinh nhật của ~Copium~. Vì vậy, mẹ ~Copium~ đã quyết định tổ chức một bữa tiệc thật hoành tráng để chúc mừng sinh nhật con trai mình và mời tất cả mọi người trong làng đến tham dự.

Do quy mô bữa tiệc rất lớn nên chiếc bánh sinh nhật được mẹ ~Copium~ chuẩn bị cũng rất đặc biệt. Cụ thể, chiếc bánh là một hình chữ nhật khổng lồ có kích thước ~N \times M~. Biết tin, ~Copium~ băn khoăn không biết chia bánh như thế nào cho hợp lý. Sau ~7749~ bước suy nghĩ, ~Copium~ quyết định dùng đúng ~X~ đường cắt ngang và ~Y~ đường cắt dọc để chia chiếc bánh thành những miếng bánh nhỏ hơn. (Tất cả đường cắt đều song song với cạnh chiếc bánh.)

Để chiếc bánh trông thật ngon và chia đều được cho mọi người thì:

• Không có ~2~ đường cắt nào trùng nhau.
• Mọi đường cắt ngang có độ dài bằng ~M~, mọi đường cắt dọc có độ dài bằng ~N~.
• Mỗi miếng bánh là một hình chữ nhật có độ dài ~2~ cạnh đều là số nguyên dương và diện tích ~\ge S~.

~Copium~ cảm thấy bài toàn này quá đơn giản, cậu nghĩ ra được một bài toán khó hơn đó là đếm số cách chia bánh thỏa mãn các điều kiện trên. Mặc dù thông minh thật nhưng ~Copium~ không tài nào đếm được do số cách chia quá lớn. Là một lập trình viên pro, bạn hãy lập trình giúp ~Copium~ giải bài toán này nhé.

Lưu ý:

• Do số cách chia quá lớn nên kết quả in ra là phần dư của đáp án khi chia cho ~10^9 + 7~.
• ~2~ cách chia được gọi là khác nếu nhau nếu có ít nhất ~1~ đường cắt dọc hoặc ~1~ đường cắt ngang ở vị trí khác nhau.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số lượng truy vấn ~(1 \le t \le 10^4)~.
• ~t~ dòng tiếp theo, dòng thứ ~i~ gồm ~5~ số nguyên ~N, M, X, Y, S~ là ~5~ số nguyên thể hiện truy vấn thứ ~i~ ~(1 \le N, M, X, Y, S \le 10^6)~.

Output

• In ra ~t~ dòng, mỗi dòng một số nguyên là kết quả của truy vấn tương ứng.

Scoring

• ~40\%~ số test có ~t \le 10~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

1
3 3 2 2 1

Sample Output

1

Cho ~1~ lưới điểm hình chữ nhật có ~n~ hàng và ~m~ cột nằm cách đều nhau, điểm ~(i,\ j)~ là giao của hàng ~i~ và cột ~j~. Mỗi điểm ~(i,\ j)~ sẽ được gán một giá trị tương ứng ~a[i][j]~. Ta định nghĩa square sum của một lưới điểm như sau :

• Ban đầu square sum bằng ~0~.
• Duyệt qua các bộ ~4~ điểm phân biệt trên lưới, nếu dựng được một hình vuông nhận ~4~ điểm này làm đỉnh thì cộng thêm giá trị ~a[i][j]~ của ~4~ điểm đấy vào square sum.

Lưu ý: Cạnh hình vuông KHÔNG NHẤT THIẾT phải nằm song song với ~2~ cạnh của lưới. (tham khảo hình vẽ bên dưới)

Cho các truy vấn có dạng ~(x1,\ y1)~, ~(x2,\ y2)~, mỗi truy vấn hỏi square sum của lưới điểm hình chữ nhật có góc trái trên ~(x1,\ y1)~ và góc phải dưới ~(x2,\ y2)~.

Vì số truy vấn tương đối lớn nên các truy vấn trong bài được nén lại dưới dạng nhóm như sau :

• Mỗi điểm ~(i,\ j)~ được gán một màu tương ứng là ~c[i][j]~.
• Ta định nghĩa bounding box của hai điểm trên lưới là hình chữ nhật nhỏ nhất về diện tích chứa cả hai điểm đó và có cạnh song song với cạnh của lưới. Lưu ý rằng diện tích của bounding box có thể = 0.
• Cho ~q~ nhóm truy vấn, mỗi nhóm được biểu diễn bởi một cặp số ~c1,\ c2~. Theo đó, xét toàn bộ các cặp điểm được tạo bởi một điểm có màu ~c1~ với ~1~ điểm có màu ~c2~ rồi tìm bounding box tương ứng của chúng. Tính kết quả của truy vấn sao cho ~(x1,\ y1)~, ~(x2,\ y2)~ chính là góc trái trên và phải dưới của bounding box được xét.
• Kết quả của một nhóm truy vấn là tổng XOR kết quả từng truy vấn trong nhóm đó. Có thể chứng minh được rằng tổng XOR sẽ không vượt quá ~2^{63} – 1~.

Input

• Dòng đầu tiên gồm ~3~ số nguyên ~n,\ m,\ q~ ~(1\le n, m \le 10^5, 1 \le n * m \le 10^5)~ ~(1 \le q \le 10^5)~ ~-~ lần lượt là số hàng, cột trong lưới điểm và số nhóm truy vấn.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên tương ứng là giá trị ~a[i][j]~ của mỗi điểm ~(1 \le a[i][j] \le 10^9)~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên tương ứng là màu ~c[i][j]~ được gán cho mỗi điểm ~(1 \le c[i][j] \le 10^5)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm một cặp số ~c1,\ c2~ (~c1 \neq c2~) biểu diễn hai màu của một nhóm truy vấn. Tổng số truy vấn ở ~q~ nhóm sẽ không vượt quá ~10^7~.

Output

• In ra ~q~ dòng, dòng thứ ~i~ là kết quả tương ứng của nhóm truy vấn thứ ~i~, hay nói cách khác, tính tổng XOR kết quả từng truy vấn trong nhóm truy vấn thứ ~i~.

Sample Input

3 3 2
1 1 1
1 1 2
1 1 1
1 2 3
4 5 8
7 8 9
1 8
9 1

Sample Output

1
27

Subtask

• 20% số test có ~a[i][j] = 1~ ở mọi điểm trên lưới
• 20% số test khác đảm bảo mỗi điểm được gán một màu ~c[i][j]~ riêng biệt
• 60% số test còn lại không có điều kiện gì thêm

Note

Giải thích sample test

• Nhóm query ~(1, 8)~ bao gồm ~2~ truy vấn :
• Trái trên ~(1, 1)~ và phải dưới ~(2, 3)~, kết quả là ~9~
• Trái trên ~(1, 1)~ và phải dưới ~(3, 2)~, kết quả là ~8~
• Tổng XOR : 9 ~\oplus~ 8 = 1
• Nhóm query ~(9, 1)~ bao gồm duy nhất ~1~ truy vấn :
• Trái trên ~(1, 1)~ và phải dưới ~(3, 3)~, kết quả là ~27~
• Tổng XOR : 27