LQDOJ CUP 2022 - Round 4

Quang được giao cho một việc, đó là lưu lại một hoán vị \(p\) của dãy số nguyên \((1,2,\ldots,n)\). Do cảm thấy việc này rất nhàm chán nên Quang đã nén hoán vị này theo một cách mà Quang tự nghĩ ra. Cách nén của Quang là chọn một số nguyên \(k\) và chỉ lưu lại tổng các đoạn con liên tiếp độ dài \(k\) của \(p\). Nói cách khác thì bây giờ Quang có một dãy số nguyên \(s = (s_{1}, s_{2}, \ldots, s_{n - k + 1})\), với

• \(s_{1} = p_{1} + p_{2} + \ldots + p_{k}\)
• \(s_{2} = p_{2} + p_{3} + \ldots + p_{k + 1}\)
• \(\ldots\)
• \(s_{n - k + 1} = p_{n - k + 1} + p_{n - k + 2} + \ldots + p_{n}\)

Quang nhanh chóng nhận ra là cách nén của anh ấy có gì đó không đúng. Cách nén trên bị một vấn đề là có thể có nhiều hoán vị có thể cùng được nén thành một dãy số. Do vậy Quang cần lưu thêm một số \(x\), có nghĩa là trong các hoán vị nén thành dãy \(s\), thì hoán vị \(p\) là hoán vị bé thứ \(x\) theo thứ tự từ điển. Do Quang có thể nhầm lẫn nên đôi khi không thể tìm thấy hoán vị thỏa mãn.

Bạn hãy giúp Quang viết một chương trình tìm hoán vị \(p\) thỏa mãn yêu cầu trên.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \leq t \leq 100000)\) là số lượng test.
• Tiếp theo là \(t\) test. Mỗi test có định dạng sau:
  • Dòng đầu tiên chứa ba số nguyên \(n\), \(k\) và \(x\) \((2 \leq n \leq 250000, 2 \leq k \leq \min(n, 6), 1 \leq x \leq 10^{18})\) .
  • Dòng tiếp theo chứa \(n - k + 1\) số nguyên \(s_{1}, s_{2}, \ldots s_{n - k + 1}\) \((1 \leq s_{i} \leq 1500000)\) là các phần tử của dãy \(s\).
• Tổng giá trị \(n\) trong các test không vượt quá \(250000\).

Output

• Với mỗi test, in ra trên một dòng \(n\) số nguyên là hoán vị thỏa mãn. Nếu không tồn tại, in ra \(-1\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 2\), \(n \leq 5000\) và tổng giá trị \(n\) trong các test không vượt quá \(5000\).
• Subtask \(2\) (\(20\%\) số điểm): \(k = 2\), \(n \leq 100000\) và tổng giá trị \(n\) trong các test không vượt quá \(100000\).
• Subtask \(3\) (\(30\%\) số điểm): \(k = 3\), \(n \leq 100000\) và tổng giá trị \(n\) trong các test không vượt quá \(100000\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
5 3 1
6 10 11
5 3 2
6 10 11

1 3 2 5 4
-1

KhaiTCL và Theanhto là đôi bạn thân. Một ngày nọ, cả hai cùng học được tính chất khá là hay ho của một chuỗi đối xứng đó là khi đảo ngược lại tất cả các kí tự thì nó cũng tạo thành một chuỗi bằng với chuỗi ban đầu. Sau đó, KhaiTCL chọn một số nguyên \(k\) và đố Theanhto đếm được số lượng xâu đối xứng độ dài \(k\) chỉ gồm các ký tự Latinh in thường (a \(\rightarrow\) z).

Điều này quả thực quá dễ đối với Theanhto, cậu ấy đã tính toán rất nhanh chỉ trong vòng một nốt nhạc. Các bạn có thể nghĩ xem kết quả ở đây là gì? Tuy nhiên, để tăng độ khó cho việc tính toán, KhaiTCL lại sinh ra \(n\) xâu \(s_1,s_2,\ldots,s_n\) và mỗi xâu cũng chỉ gồm các ký tự Latinh in thường. Lúc này KhaiTCL muốn Theanhto tính xem có bao nhiêu xâu đối xứng mà ít nhất \(1\) trong \(n\) xâu \(s_1,s_2,\ldots,s_n\) này xuất hiện trong xâu đối xứng đó ít nhất \(1\) lần. KhaiTCL định nghĩa xâu \(a\) xuất hiện trong xâu \(b\) nếu tồn tại vị trí \(i \in [1,|b|-|a|+1]\) mà \(a_j = b_{i+j-1} \ \forall j \in [1,|a|]\), ở đây mỗi xâu có các kí tự được đánh chỉ số từ \(1\) từ trái qua phải và \(|t|\) là độ dài của xâu \(t\) nào đó.

Do KhaiTCL thấy hơi hụt hẫng khi Theanhto giải được bài tập đầu tiên quá nhanh nên cậu mới nghĩ ra bài toán thứ hai nhưng thật không may khi bài toán này chính cậu cũng không biết phải đếm như thế nào kể cả khi cậu có một cái máy tính trong tay để lập trình. Thông qua cuộc thi LQDOJ CUP, KhaiTCL quyết định tìm đến những lập trình viên giỏi nhất nhằm giúp KhaiTCL giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 10 ^ 3\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_i\) (\(1 \leq |s_i| \leq 10 ^ 3\)).
• Tổng độ dài các xâu \(s_i\) không vượt quá \(10 ^ 3\).

Output

• Một dòng duy nhất chứa một số nguyên là phần dư của kết quả bài toán khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|s_1| = |s_2| = \ldots = |s_n| = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n = 1\) và \(|s_1| = 2\).
• Subtask \(3\) (\(20\%\) số điểm): \(n=1\).
• Subtask \(4\) (\(20\%\) số điểm): \(|s_i| \leq 20 \ \forall i \in [1, n]\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

2 3
a
aa

51

Miền Tây hoang dã tại nước Mỹ xa xôi sắp diễn ra một cuộc thi đấu giữa những chàng cao bồi tài hoa. \(m\) chàng cao bồi phải đi tìm kiếm cho mình những chú ngựa cừ khôi như là một phần của cuộc thi.

Biết rằng mảnh đất viễn tây có thể biểu diễn dưới dạng toạ độ \(Oxy\). Cụ thể, bốn điểm \((x, y)\), \((x - 1, y)\), \((x, y - 1)\), \((x - 1, y - 1)\) sẽ tạo ra một ô vuông đơn vị. Tại một số ô vuông đơn vị sẽ có những chú ngựa đang say sưa tắm nắng. Các chàng cao bồi sẽ lần lượt chọn ra một điểm có toạ độ \((u, v)\) và thực hiện:

• Từ điểm \((u, v)\) tạo hàng rào sang trái song song với trục \(Ox\) và hàng rào xuống dưới song song với trục \(Oy\) cho đến khi chạm vào một trong hai trục hoặc một hàng rào trước đó. Cuộc thi đảm bảo toạ độ không có hai chàng cao bồi nào chọn cùng toạ độ \(u\) hoặc cùng toạ độ \(v\).
• Chàng cao bồi sẽ thu thập hết tất cả con ngựa trong mảnh đất được giới hạn bởi hàng rào từ các chàng cao bồi trước đó, hai trục \(Ox, Oy\) và hàng rào của mình vừa tạo.

Hãy tính số con ngựa mà mỗi chàng cao bồi thu thập được để ban tổ chức có thể tìm ra người chiến thắng.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 3 \cdot 10^{5})\) là số lượng con ngựa.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((1 \leq x_{i}, y_{i} \leq 10^{9})\) là tọa độ góc phải trên của ô vuông đơn vị của con ngựa thứ \(i\).
• Dòng tiếp theo chứa số nguyên \(m\) \((1 \leq m \leq 3 \cdot 10^{5})\) là số lượng chàng cao bồi tham gia cuộc thi.
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i}, v_{i} \leq 10^{9})\) là tọa độ mà chàng cao bồi thứ \(i\) chọn.

Output

• In ra \(m\) dòng, dòng thứ \(i\) chứa một số nguyên là số con ngựa mà chàng cao bồi thứ \(i\) thu thập được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(x_{1} = x_{2} = \ldots = x_{n}\) hoặc \(y_{1} = y_{2} = \ldots = y_{n}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n, m \leq 2 \cdot 10^{3}\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2
1 3
1 4
1 5
1 6
5
6 7
5 6
4 5
3 3
8 4

5
5
4
2
0

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

10
9
6
3
1