Bach Khoa Code Challenge #2
A. Truyền tin
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Đây là bài toán interactive.

Bảo đang làm tình báo, trong quá trình do tham Bảo đã thu thập được rất nhiều thông tin có giá trị và gửi về cho trụ sở chính BKCC. Tuy nhiên khi quay trở về báo cáo, Bảo phát hiện rằng tất cả dữ liệu mật báo gửi về đều đã bị lỗi và không thể sử dụng được (khiến cho Bảo bị vụt mất KPI và bị cấp trên khiển trách). Sau quá trình phân tích, Bảo phát hiện rằng do thiết bị truyền tin của mình mà tất cả thông tin mà Bảo gửi về đều có một lỗi chung như sau:

Thông tin mà Bảo gửi về có dạng là một mã nhị phân độ dài $$$n$$$, do thiết bị lỗi mà chính xác một bit trong dãy nhị phân này bị biến đổi, tức là bit $$$0$$$ thành $$$1$$$ và ngược lại.

Do không đủ tiền để sửa chữa thiết bị, Bảo quyết định gửi thêm thông tin để khắc phục vấn đề này. Thông tin mà Bảo gửi thêm là các $$$bit$$$ được đính kèm với mật mã gốc gọi là các $$$xor\_bit$$$. Mỗi $$$xor\_bit$$$ có thể chứa $$$k$$$ thông tin $$$i_1, i_2, \ldots, i_k$$$. Trong đoạn mật mã mới, nếu tại $$$pos$$$ là một $$$xor\_bit$$$ nó sẽ có giá trị bằng với $$$a_{i1} \oplus a_{i2} \oplus \ldots, a_{ik}$$$. Với $$$a_i$$$ là giá trị của bit thứ $$$i$$$ trong đoạn mật mã mới.

Đoạn mật mã mới sẽ là đoạn mật mã cũ nhưng được chèn vào các $$$xor\_bit$$$ mà bạn quy định, mà không làm mất đi thứ tự của đoạn mật mã gốc.

Do thông tin mật báo cần được bảo mật chặt chẽ, thông tin sau khi thêm các $$$xor\_bit$$$ mà Bảo có thể gửi không được vượt quá $$$n + 50$$$. Đau đầu vi không biết phải thiết kế dãy $$$xor\_bit$$$ làm sao, Bảo nhờ tới bạn giúp Bảo chọn ra các $$$xor\_bit$$$, sau đó nhận mã truyền tin của Bảo với các $$$xor\_bit$$$ mà bạn đã quy ước, và xác định bit nào bị lỗi trong quá trình truyền tin (hoặc là bit của mã ban đầu hoặc là $$$xor\_bit$$$)

Input

Dòng đầu tiên là một số nguyên dương $$$t$$$ ($$$1 \le t \le 100$$$) — Số testcases

Dòng đầu tiên của mỗi testcase gồm một số nguyên dương $$$n$$$ ($$$1 \le n \le 5000$$$) $$$-$$$ Độ dài mật mã.

Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcase không vượt quá $$$5000$$$.

Sau khi đọc vào input cho mỗi testacse, tiến hành quá trình interact như sau.

Interaction

Với mỗi testcase, thực hiện những điều dưới đây.

Nếu sử dụng $$$k$$$ $$$xor\_bit$$$, hãy in dưới dạng sau:

  • $$$?$$$ $$$c$$$ ($$$0 \le c \le 50$$$) $$$-$$$ Số $$$xor\_bit$$$ sẽ được sử dụng.

Sau đó in ra $$$c$$$ dòng, mỗi dòng có dạng sau:

  • $$$?$$$ $$$pos$$$ $$$k$$$ $$$i_1, i_2, \ldots i_k$$$ ($$$0 \le k \le n$$$, $$$1 \le pos \le n + c$$$, $$$1 \le i_j \le n + c$$$, mọi $$$i_j$$$ đều đôi một khác nhau) - Lần lượt là vị trí của $$$xor\_bit$$$ trong mật mã bạn nhận được, số lượng thông tin mà $$$xor\_bit$$$ đó chứa và các thông tin của $$$xor\_bit$$$ đó.

Nếu $$$k = 0$$$ thì $$$xor\_bit = 0$$$.

Lưu ý, các các thông tin của $$$xor\_bit$$$ không thể là vị trí một $$$xor\_bit$$$ nào đó. Hay $$$i, pos$$$ đều phải thõa $$$i \neq pos$$$ với $$$i$$$ là thông tin của một $$$xor\_bit$$$ và $$$pos$$$ là vị trí của $$$xor\_bit$$$ nào đó trong mật mã mới. Đồng thời, các vị trí $$$pos$$$ của các $$$xor\_bit$$$ cũng phải đôi một khác nhau.

Khi đã in ra đầy đủ các thông tin, hãy đọc vào $$$n + c$$$ giá trị $$$a_1, a_2, \ldots a_{n + c}$$$ ($$$a_i \in \{0, 1\}$$$) $$$-$$$ Đoạn mật mã sau sau khi Bảo gửi cho bạn, trong đó có một bit đã bị sai thông tin so với đoạn mật mã gốc.

Nếu bạn biết được vị trí của bit bị sai, hãy in ra một dòng dưới dạng sau: $$$!$$$ $$$id$$$ ($$$1 \le id \le n + c$$$).

Sau khi thực hiện một một thao tác hãy nhớ in ra ký tự xuống dòng và flush output. Nếu không bạn có thể gặp Idleness limit exceeded hoặc các kết quả khác. Để làm điều này, hãy sử dụng:

  • fflush(stdout) hoặc cout.flush() trong C++;
  • System.out.flush() trong Java;
  • flush(output) trong Pascal;
  • stdout.flush() trong Python;
  • xem tài liệu đối với các ngôn ngữ khác.

Khuyến khích các bạn đọc thêm tài liệu về hướng dẫn dành cho các bài toán interactive.

Example
Input
3
1
5
3
Output
? 2

? 1 1 3

? 2 1 3

! 2

? 1

? 1 4 2 3 4 5 6

! 6

? 0

! 3
Note

Lưu ý: Đây không phải là các bước để giải bài toán này, đây là ví dụ về cách tương tác với máy chấm.

Ở ví dụ thứ nhất, nhập vào $$$n = 1$$$, lúc này đưa ra các thông tin sau:

  • $$$?$$$ $$$2$$$ $$$-$$$ sẽ có $$$2$$$ $$$xor\_bit$$$ được sử dụng.
  • $$$?$$$ $$$1$$$ $$$1$$$ $$$3$$$ $$$-$$$ $$$xor\_bit$$$ sẽ ở vị trí $$$1$$$ và ảnh hưởng đến bit thông tin ở vị trí $$$3$$$.
  • $$$?$$$ $$$2$$$ $$$1$$$ $$$3$$$ $$$-$$$ $$$xor\_bit$$$ sẽ ở vị trí $$$2$$$ và ảnh hưởng đến bit thông tin ở vị trí $$$3$$$.
Giả sử thông tin ban đầu là [$$$1$$$], lúc này ta có thông tin mới là $$$[\underline{1}, \underline{1}, 1]$$$ (các bit được gạch chân là $$$xor\_bit$$$). Tuy nhiên sau khi nhận được thông tin, bạn thu được $$$[\underline{1}, \underline{0}, 1]$$$. lúc này, bit bị sai nằm ở vị trí $$$2$$$, in ra $$$!$$$ $$$2$$$.

Ở ví dụ thứ hai, nhập vào $$$n = 5$$$, giả sử dãy bit ban đầu là $$$[1, 0, 0, 1, 0]$$$. Sau khi thêm $$$xor\_bit$$$, nó trở thành $$$[\underline{0}, 1, 0, 0, 1, 0]$$$, lúc này qua truyền tin nó trở thành $$$[\underline{0}, 1, 0, 0, 1, 1]$$$. Lúc này bit bị sai nằm ở vị trí $$$6$$$, in ra $$$!$$$ $$$6$$$.

Ở ví dụ thứ ba, nhập vào $$$n = 3$$$, giả sử dãy ban đầu là $$$[0, 0, 1]$$$, bạn bằng cách thần kì nào đó không cần $$$xor\_bit$$$, sau khi qua truyền tin nó trở thành $$$[1, 0, 1]$$$. Lúc này bạn in ra $$$!$$$ $$$1$$$.

B. Noisy Cat
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Một ngày nọ, một bức ảnh đen trắng của chú mèo dễ thương bị lỗi trong quá trình truyền dẫn và gây ra nhiễu. Bức ảnh được biểu diễn bởi ma trận $$$n \times m$$$, mỗi phần tử là một giá trị nguyên từ $$$0$$$ đến $$$10^9$$$, tương ứng với độ sáng của một pixel ($$$0$$$ là đen hoàn toàn, $$$10^9$$$ là trắng hoàn toàn).

Nhiệm vụ của bạn là giúp ảnh của chú mèo trở lại xinh đẹp như ban đầu bằng cách áp dụng bộ lọc trung vị (median filter) kích thước $$$k \times k$$$. Cụ thể, với mỗi vùng $$$k \times k$$$, bạn sẽ thay thế giá trị của ô trung tâm với trung vị của $$$k^2$$$ pixel trong vùng đó.

Lưu ý, bộ lọc trung vị sẽ được áp dụng đồng thời cho mọi pixel.

Giá trị trung vị của một dãy có số phần tử lẻ là số nằm chính giữa dãy đó sau khi đã sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy [$$$1, 5, 2, 3, 5$$$] là $$$3$$$.

Các pixel khác (không đủ khung $$$k \times k$$$) sẽ giữ nguyên.

Input

Dòng đầu tiên gồm một số nguyên $$$t$$$ ($$$1 \le t \le 1000$$$) — số testcase, mô tả của mỗi testcase như sau.

Dòng đầu tiên của mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$m$$$ và $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le \mathrm{min}(n, m)$$$, $$$k$$$ là một số lẻ) — số hàng, số cột và kích thước cạnh của bộ lọc trung vị.

$$$n$$$ dòng tiếp theo của mỗi testcase gồm $$$m$$$ số nguyên $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$0 \le a_{ij} \le 10^9$$$) — độ sáng của mỗi pixel.

Dữ liệu vào bảo đảm tổng $$$n \times m \le 2 \cdot 10^5$$$ trong mọi testcases.

Output

Với mỗi testcase, in ra $$$n$$$ dòng, mỗi dòng có $$$m$$$ ký tự cho biết độ sáng của mỗi pixel sau khi đã lọc trung vị.

Example
Input
3
3 3 3
20 30 25
40 255 35
22 28 26
4 5 3
83 3 75 32 42
32 16 3 50 29
86 6 73 32 77
3 83 16 42 50
1 1 1
10
Output
20 30 25
40 28 35
22 28 26
83 3 75 32 42
32 32 32 42 29
86 16 32 42 77
3 83 16 42 50
10
Note

Ở ví dụ thứ nhất, chỉ có một ô sẽ được áp dụng bộ lọc, nằm tại vị trí ($$$2, 2$$$). Chọn ra các ô trong vùng $$$3 \times 3$$$ ta có: dãy [$$$20, 22, 25, 26, 28, 30, 35, 40, 255$$$], thay thế giá trị của ô ($$$2, 2$$$) từ $$$255$$$ thành $$$28$$$. Các ô còn lại giữ nguyên.

C. Dán gỗ
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thầy Tuấn đang có $$$n$$$ tấm gỗ được đánh số từ $$$1$$$ đến $$$n$$$ có chiều rộng là $$$w_i$$$ chiều cao là $$$h_i$$$. Do sợ tốn tiền mua sơn nên thầy giao nhiệm vụ cho em Bảo phải mua giấy dán cho những tấm gỗ này.

Hiện tại Bảo xác định được trong cửa hàng đang có các miếng dán kích thước cụ thể là $$$R \times C$$$, tức là độ rộng là $$$R$$$ và chiều cao là $$$C$$$. Do đã in banner BKAC nên Bảo không thể xoay chiều được miếng dán.

Biết rằng khi dán, mỗi miếng chỉ có thể nằm gọn trên một tấm gỗ, không có trường hợp dán cho hai hoặc nhiều tấm cùng lúc. Ngoài ra miếng dán không được đổi chiều (xoay miếng dán) và các cạnh miếng dán phải song song với các cạnh tấm gỗ.

Hãy cho biết số miếng dán ít nhất cần để các tấm gỗ đều được dán kín.

Input

Dòng đầu tiên gồm duy nhất một số nguyên dương $$$t$$$ ($$$1 \le t \le 1000$$$) $$$-$$$ số lượng testcases, mỗi testcase gồm ba dòng.

Dòng đầu tiên của mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$R$$$ và $$$C$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le R, C \le 10^{9}$$$) $$$-$$$ số lượng các tấm gỗ và kích thước của miếng dán.

Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) $$$-$$$ chiều cao của mỗi tấm gỗ.

Dòng thứ ba của mỗi testcase gồm $$$n$$$ số nguyên $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^9$$$) $$$-$$$ chiều rộng của mỗi tấm gỗ.

Dữ liệu đầu vào bảo đảm tổng $$$n$$$ ở mọi testcase không vượt quá $$$2 \cdot 10^5$$$.

Output

Với mỗi testcase, trên một dòng, in ra số lượng miếng dán cần dùng.

Example
Input
6
2 20 3
12 12
40 100
1 1 1
4
2
8 11 10
10 10 10 10 10 40 50 20
55 11 55 55 22 33 33 44
3 7 8
34 41 39
30 26 9
6 233476014 803143630
6847813 323424606 946007923 753712436 361958625 65047772
410767748 684568549 39950281 892753411 349000147 698300063
2 92526808 107236580
539839331 967415484
606720335 187353153
Output
28
8
53
59
16
72
Note

Ở ví dụ thứ nhất, tấm gỗ đầu tiên cần $$$8$$$ miếng dán và tấm gỗ thứ hai cần $$$20$$$ miếng dán. Tổng số miếng dán cần dùng là $$$28$$$.

Ở ví dụ thứ hai, cần $$$8$$$ miếng dán cho duy nhất một tấm gỗ.

Ở ví dụ thứ tư, các tấm gỗ lần lượt cần $$$25$$$, $$$24$$$ và $$$10$$$ miếng dán, tổng số miếng dán cần dùng là $$$59$$$.

D. Bảo và các triết gia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bảo được vinh dự mời vào bàn ăn của các triết gia. Bàn ăn là một chiếc bàn tròn với $$$n$$$ chỗ ngồi và hiện tại đang có $$$m$$$ người (tính luôn cả Bảo) đang ngồi trong bàn ở vị trí $$$a_1, a_2, \ldots a_m$$$ ($$$a_i$$$ khác nhau đôi một).

Hiện tại đang có $$$t$$$ chiếc đũa nằm ở vị trí $$$b_1, b_2, \ldots, b_t$$$ ($$$b_i$$$ khác nhau đôi một). Biết rằng một người trong bàn chỉ có thể ăn nếu họ lấy được một đôi đũa. Hãy cho biết liệu tất cả mọi người đều có thể ăn cùng lúc hay không.

Người ngồi ở chỗ ngồi $$$i$$$ ($$$1 \lt i \lt n$$$) sẽ có thể sử dụng chiếc đũa ở vị trí thứ $$$i - 1$$$, $$$i$$$ và $$$i + 1$$$. Người ngồi ở chỗ ngồi $$$n$$$ sẽ có thể sử dụng chiếc đũa ở vị trí $$$n - 1$$$, $$$n$$$ và $$$1$$$. Người ngồi ở chỗ ngồi $$$1$$$ sẽ có thể sử dụng chiếc đũa ở vị trí $$$n$$$, $$$1$$$ và $$$2$$$. Một chiếc đũa chỉ có thể được sử dụng bởi một người.

Input

Dòng đầu tiên là một số nguyên dương $$$t$$$ ($$$1 \le t \le 500$$$) $$$-$$$ số testcase, mô tả của mỗi testcase như sau.

Dòng đầu tiên của mỗi testcase là ba số nguyên dương $$$n$$$, $$$m$$$ và $$$t$$$ ($$$3 \le m, t \le n \le 100$$$) $$$-$$$ số chỗ ngồi trong bàn, số người ăn và số chiếc đũa.

Dòng thứ hai của mỗi testcase là $$$m$$$ số nguyên dương $$$a_1, a_2, \ldots a_m$$$ ($$$1 \le a_i \le n$$$, $$$a_i$$$ khác nhau đôi một) $$$-$$$ vị trí ngồi của mỗi người.

Dòng thứ ba của mỗi testcase là $$$t$$$ số nguyên dương $$$b_1, b_2, \ldots b_t$$$ ($$$1 \le b_i \le n$$$, $$$b_i$$$ khác nhau đôi một) $$$-$$$ vị trí của các chiếc đũa.

Output

Với mỗi testcase, trên một dòng, in ra YES hoặc NO tương ứng với việc tất cả mọi người có thể cùng ăn hay không.

Example
Input
4
10 3 7
2 7 10
9 3 8 1 7 2 10
4 4 4
1 2 3 4
1 2 3 4
8 4 8
2 4 6 7
1 2 3 4 5 6 7 8
8 3 6
2 5 8
1 3 4 5 7 8
Output
YES
NO
YES
YES
Note

Ở ví dụ thứ nhất, người thứ $$$1$$$ ngồi ở vị trí $$$2$$$ và sử dụng chiếc đũa tại $$$2$$$ và $$$3$$$. Người thứ $$$2$$$ ngồi ở vị trí $$$7$$$ và sử dụng chiếc đũa tại $$$7$$$ và $$$8$$$. Người thứ $$$3$$$ ngồi ở vị trí $$$10$$$ và sử dụng chiếc đũa tại $$$10$$$ và $$$1$$$. Tất cả mọi người đều có thể dùng bữa.

Ở ví dụ thứ hai, người thứ $$$1$$$ ngồi ở vị trí $$$1$$$ và sử dụng chiếc đũa tại $$$1$$$ và $$$2$$$, người thứ $$$3$$$ sử dụng chiếc đũa tại $$$3$$$ và $$$4$$$. Người thứ $$$2$$$ và $$$4$$$ không thể dùng bữa.

E. Đếm số đoạn con
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cho một dãy số nguyên $$$a$$$ gồm $$$n$$$ phần tử. Một đoạn con (subarray) là một dãy liên tiếp không rỗng các phần tử của mảng, và đoạn con được gọi là tốt nếu trong nó có chính xác k giá trị phân biệt.

Nhiệm vụ của bạn là đếm xem có bao nhiêu đoạn con tốt của mảng được cho.

Input

Dòng đầu tiên chứa một số nguyên $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$) — số lượng truy vấn. Với mỗi truy vấn:

  • Dòng đầu chứa hai số nguyên $$$n$$$ và $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^{5}$$$).
  • Dòng thứ hai chứa $$$n$$$ số nguyên $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \leq a_{i} \leq 10^{9}$$$).

Dữ liệu vào bảo đảm tổng $$$n$$$ trong mọi testcase không vượt quá $$$2 \cdot 10^5$$$.

Output

Đối với mỗi truy vấn, in ra một dòng duy nhất — số đoạn con chứa chính xác $$$k$$$ giá trị phân biệt.

Example
Input
3
1 1
10
3 1
3 1 8
16 1
8 1 5 8 8 7 4 9 7 10 10 7 5 8 5 5
Output
1
3
19

F. Ngắm hoa anh đào
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nhà Chung có một khu vườn vô cùng tuyệt đẹp. Ở đó, Chung trồng $$$n$$$ cây anh đào tạo thành một vòng tròn. Chung đánh số các cây từ $$$1$$$ đến $$$n$$$. Chung đánh giá cây thứ $$$i$$$ có độ "đẹp" là $$$h_i$$$.

Chung đứng ở trung tâm của vườn hoa và muốn ngắm nhìn hàng cây anh đào của mình. Chung muốn ngắm các cây anh đào của mình. Chung có một số quy tắc rất kì lạ như sau:

  • Chung sẽ bắt đầu quá trình ngắm cây của mình tại một cây anh đào bất kì.
  • Sau khi ngắm xong cây thứ $$$i$$$, Chung sẽ quay sang ngắm cây thứ $$$a_i$$$ ở bên trái hoặc bên phải.
  • Trong quá trình quay, Chung không ngắm những cây ở giữa.
  • Mỗi cây, dù có thể được ngắm nhiều lần, chỉ được tính độ "đẹp" một lần.

Hãy giúp Chung tìm cách cách ngắm các cây để đạt được tổng độ "đẹp" lớn nhất.

Input

Dòng đầu tiên chứa một số nguyên dương $$$t$$$ ($$$1 \le t \le 10^4$$$)— số testcases.

Mỗi testcase được mô tả như sau:

  • Dòng đầu tiên chứa một số nguyên dương $$$n$$$ ($$$2 \le n \le 2 \times 10^5$$$) — số cây anh đào trong khu vườn nhà Chung.
  • Dòng thứ hai chứa $$$n$$$ số nguyên dương $$$h_1,h_2,\cdots,h_n$$$ ($$$1 \le h_i \le 10^9$$$) — độ "đẹp" của các cây anh đào.
  • Dòng thứ ba chứa $$$n$$$ số nguyên dương $$$a_1,a_2,\cdots,a_n$$$ ($$$1 \le a_i \lt n$$$).

Dữ liệu đảm bảo tổng $$$n$$$ trong tất cả các testcases không vượt quá $$$2 \times 10^5$$$.

Output

Với mỗi testcase, in ra một số nguyên dương duy nhất — Tổng độ "đẹp" lớn nhất có thể đạt được.

Example
Input
1
5
3 5 4 2 3
2 1 3 1 1
Output
17
Note

Ở ví dụ mẫu, quá trình quay của Chung là: $$$2 \rightarrow 1 \rightarrow 4 \rightarrow 3 \rightarrow 5.$$$

G. Dãy số GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chung rất lười ra đề nhưng vì bị chích điện tâm huyết với BKCC#2, Chung quyết định ra một bài toán rất dễ như sau:

Với hai số nguyên dương $$$T$$$, Chung định nghĩa dãy $$$a$$$ vô hạn phần tử, đánh số từ $$$0$$$, theo nguyên tắc sau:

  • $$$a_0 = a_1 = T$$$.
  • $$$a_i$$$ = $$$\gcd(a_0 \times a_1 \times \cdots \times a_{\lfloor\frac{i}{2}\rfloor - 1}, a_{\lfloor\frac{i}{2}\rfloor} \times \cdots \times a_{i-1})$$$ $$$(\forall i \ge 2)$$$.

Mỗi bộ testcase, Chung cho bạn hai số nguyên dương $$$T, n$$$ và bạn được yêu cầu tính giá trị của $$$a_n$$$ với T được cho, chia lấy dư cho $$$10^9 + 7$$$.

Input

Dòng đầu tiên chứa số nguyên dương $$$t$$$ ($$$t \le 10^4$$$) — số testcase.

$$$t$$$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $$$T, n$$$ ($$$2 \le T \le 10^9, 2 \le n \le 10^6$$$) — Dữ liệu của bài toán.

Dữ liệu bài toán đảm bảo rằng tổng $$$n$$$ trong mọi testcase không vượt quá $$$10^6$$$.

Output

Mỗi testcase in ra một số nguyên dương — đáp án của bài toán.

Example
Input
1
5 6
Output
125
Note

Với $$$T = 5$$$, dãy số $$$a$$$ như sau: $$$5, 5, 5, 5, 25, 25, 125$$$.

H. Bàn cờ
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Chung có 1 bàn cờ kích thước $$$n \times n$$$. Trên bàn cờ đó, Chung muốn đặt $$$k$$$ quân cờ. Con cờ thứ $$$i$$$ đặt ở ô ($$$r_i,c_i$$$). Chung có thể đặt 2 loại quân cờ: Xe hoặc Tượng.

Chung thắc mắc rằng, có bao nhiêu cách đặt quân cờ sao cho sau khi đặt, không quân cờ nào có thể bị ăn bởi quân cờ khác.

Input

Dòng đầu tiên chứa một số nguyên dương $$$t$$$ — số testcase.

Mỗi bộ test được mô tả như sau:

  • Dòng đầu tiên chứa 2 số nguyên dương $$$n,k$$$ ($$$1 \le n \le 10^{12}$$$), ($$$1 \le k \le 10^6$$$) — Kích thước của bàn cờ và số quân cờ cần đặt vào bàn cờ.
  • $$$k$$$ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương $$$r_i,c_i$$$ ($$$1 \le r_i,c_i \le n$$$) — Vị trí của quân cờ thứ $$$i$$$.

Dữ liệu đầu vào đảm bảo vị trí $$$k$$$ quân cờ đôi một phân biệt.

Tổng $$$k$$$ trong tất cả các testcase không vượt quá $$$10^6$$$.

Output

Với mỗi testcase, hãy in ra số cách đặt quân cờ thỏa mãn yêu cầu bài toán chia lấy dư cho $$$10^9 + 7$$$.

Example
Input
2
10 3
1 3
2 4
10 10
10 5
1 1
5 3
7 5
9 2
10 10
Output
2
2
Note

Ở ví dụ 1, có 2 cách đặt quân cờ vào các ô thứ nhất, hai, ba như sau: Xe, Xe, Xe hoặc Xe, Xe, Tượng.

Ở ví dụ 2, có 2 cách là: Xe, Xe, Xe, Xe, Xe hoặc Xe, Xe, Xe, Tượng, Xe.

I. Di chuyển trên lưới
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Trong một tựa game do Bảo làm ra, bản đồ game là một lưới gồm $$$n$$$ cột, với cột thứ $$$i$$$ chỉ tồn tại các ô từ tọa độ $$$(1, i), (2, i), \ldots, (a_i, i)$$$. Biết rằng ô ($$$i, j$$$) ở hàng thứ $$$i$$$ tính từ trên xuống dưới và cột thứ $$$j$$$ tính từ trái sang phải.

Giả sử nhân vật của bạn đang ở trong bản đồ game, và ở ô ($$$i, j$$$). Bảo có thể thực hiện các thao tác sau:

  • Nếu tồn tại ô ở tọa độ ($$$i + 1, j$$$), di chuyển đến nó và tốn $$$1$$$ đồng.
  • Nếu tồn tại ô ở tọa độ ($$$i - 1, j$$$), di chuyển đến nó và tốn $$$1$$$ đồng.
  • Nếu tồn tại ô ở tọa độ ($$$i, j + 1$$$), di chuyển đến nó và không tốn chi phí.
  • Nếu tồn tại ô ở tọa độ ($$$i, j - 1$$$), di chuyển đến nó và không tốn chi phí.
Định nghĩa $$$f(i, j)$$$ là chi phí ít nhất để nhân vật di chuyển từ ô ($$$a_i, i$$$) đến ô ($$$a_j, j$$$) sử dụng các thao tác trên. Hãy giúp Bảo tính: $$$$$$\sum_{i = 1}^{n}\sum_{j = i + 1}^{n} f(i, j)$$$$$$
Input

Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 10^4$$$) $$$-$$$ số testcases.

Dòng đầu tiên của mỗi testcase gồm một số nguyên dương duy nhất $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số cột của lưới.

Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên dương $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) $$$-$$$ độ cao của mỗi cột.

Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$.

Output

Với mỗi testcase, trên một dòng, in ra kết quả của bài toán.

Example
Input
2
3
3 2 1
5
2 5 4 1 3
Output
4
30