Am hiểu sâu sắc và có lòng tin mãnh liệt vào phương pháp bảo vệ sức khỏe bằng tập luyện TDTT, Bác Hồ khuyên mỗi người dân: "Mỗi ngày lúc ngủ dậy, tập một ít thể dục. Ngày nào cũng tập, khí huyết lưu thông, tinh thần đầy đủ, như vậy là sức khỏe…" . Điều Bác nói cách chúng ta hơn nửa thế kỷ này lại rất gần với định nghĩa về sức khỏe của Tổ chức Y tế thế giới ngày nay "Sức khoẻ là một trạng thái hoàn toàn thoải mái cả về thể chất, tâm thần và xã hội, chứ không phải là chỉ là không có bệnh tật hay tàn phế".

Chính vì thế, Copium luôn chăm chỉ rèn luyện sức khỏe mỗi ngày. Ở phòng tập có ~n~ quả tạ được đánh số từ ~1~ đến ~n~, mỗi quả tạ đều được ghi số cân nặng lần lượt là ~w_1, w_2, \dots, w_n~. Copium vốn là một gymer nổi tiếng với biệt tài nâng được ~3~ quả tạ cùng lúc mà không ai có thể làm được. Bên cạnh đó, do tập tạ đã lâu nên Copium có thể nâng tổng cân nặng lên tới ~M~. Là một stalker fan hâm mộ nhiệt thành của Copium, bạn hãy tính với nhiều nhất là ~3~ quả tạ từ số tạ cho trước, Copium có thể nâng bao nhiêu hạng cân khác nhau bé hơn hoặc bằng ~M~.

Biết rằng hạng cân chính là tổng số cân từ các quả tạ mà Copium phải nâng.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ ~(1 \leq n \leq 300)~ và ~M~ ~(1 \leq M \leq 10^6)~.
• Dòng thứ hai bao gồm ~n~ số nguyên là ~w_1, w_2, \dots, w_n~ ~(1 \leq w_i \leq 10^6)~.

Output

• Gồm một số nguyên duy nhất là số hạng cân khác nhau bé hơn hoặc bằng ~M~ mà Copium có thể nâng được.

Sample Input

4 16
5 5 5 5

Sample Output

3

Note

Bạn đã dành ra một ngày theo dõi và biết được rằng với số tạ có số cân cho trước lần lượt là ~[5, 5, 5, 5]~ thì Copium có thể nâng được các hạng cân khác nhau lần lượt từ ~5~, ~10~, ~15~. Vì các số này đều bé hơn hoặc bằng tổng cân nặng mà Copium có thể nâng được là ~16~ nên có tổng cộng ~3~ hạng cân khác nhau.

Cho dãy ~a~ gồm ~n~ phần tử và số nguyên dương ~k~, mỗi thao tác bạn được phép đổi chỗ hai phần tử ~a_i~ và ~a_{i+1}~ nếu:

• ~i < n~ .
• ~|a_i - a_{i+1}|~ không chia hết cho ~k~ .

Dãy ~a~ được gọi là xếp theo thứ tự không giảm nếu ~a_i \leq a_{i+1}~ ~(i < n)~. Bạn cần xếp lại dãy ~a~ theo thứ tự không giảm bằng các thao tác trên.

Input

• Dòng đầu của input chứa ~t~ ~(1 \leq t \leq 100)~ là số test case, mỗi test case gồm ~2~ dòng.
• Dòng đầu của mỗi test case gồm ~n~ ~(1 \leq n \leq 2 \times 10^5)~ là số phần tử của dãy và số nguyên dương ~k~ ~(1 \leq k \leq 10^9)~.
• Dòng thứ hai của mỗi test case gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^9)~ lần lượt là các phần tử của dãy ~a~.

Đảm bảo rằng tổng ~n~ của ~t~ test case không quá ~200000~.

Output

• In ra ~t~ dòng là đáp án tương ứng của mỗi test case. Đáp án là Yes nếu bạn có thể xếp lại ~a~ theo thứ tự không giảm và No trong trường hợp còn lại.

Subtask

• ~30\%~ số test có ~k = 1~.
• ~30\%~ số test tiếp theo có ~k \leq 2 \times 10^5~.
• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

2
5 7
2 1 3 5 4
5 3
4 1 1 1 1

Sample Output

Yes
No

Cho số nguyên dương ~c~ có biểu diễn nhị phân là ~1~ xâu có độ dài ~N-1~ chỉ gồm ký tự ~0~ và ~1~. Bạn cần tìm ~2~ số ~a~ và ~b~ thoả mãn điều kiện sau :

• ~a-b = c~ và ~a~ ~\&~ ~b = 0~ (với ~\&~ thể hiện toán tử AND).
• Số bit ~1~ trong biểu diễn nhị phân của ~a~ và ~b~ là bằng nhau.
• ~a, b < 2^N~.

Input

• Dòng đầu tiên gồm một số ~N~ thể hiện độ dài của xâu nhị phân ~(2 \le N \le 2 \times 10^5)~.
• Dòng tiếp theo gồm ~N-1~ ký tự ~0~ hoặc ~1~ lần lượt từ trái sang phải là bit thứ ~N-2, \dots, 1, 0~ trong biểu diễn nhị phân của ~c~ .

Output

In ra ~2~ xâu nhị phân độ dài ~N~ trên ~2~ dòng :

• Dòng đầu là biểu diễn nhị phân của số ~a~.
• Dòng thứ hai là biểu diễn nhị phân của số ~b~.

Nếu có nhiều cặp số ~(a, b)~ hợp lệ thì hãy chọn một cặp bất kỳ để in ra.

Subtask

• ~30\%~ số test có ~n \leq 15~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

11
0000000001

Sample Output

00000000010
00000000001

Note

Khi chuyển từ hệ nhị phân sang hệ thập phân ta có :

• ~a = 00000000010_2 = 2~
• ~b = 00000000001_2 = 1~
• ~c = 0000000001_2 = 1~

AP vốn dĩ là một người thích vẽ nên trước khi khai giảng AP đã kịp mua một bộ màu với ~43 252 003 274 489 856 000~ cây bút màu khác nhau. Tuy nhiên AP lại không phải là người có năng khiếu hội họa nên anh đã làm hỏng gần hết và chỉ còn lại ~200000~ cây bút. Biết tới niềm yêu thích hội họa của AP, thầy giáo môn đồ thị đã đố AP bài toán như sau :

• Cho đồ thị có hướng gồm ~n~ đỉnh và ~m~ cạnh, hãy tìm cách tô màu cho ~m~ cạnh trên đồ thị để không có chu trình nào gồm toàn các cạnh được tô cùng 1 màu.

• Vì sợ AP làm hỏng thêm bút và không thể hoàn thành câu đố nên thầy giáo muốn số màu bút mà cậu sử dụng là ít nhất.

AP đang bận đi khai giảng nên mọi người hãy giúp cậu nhé !! Mai là AP vào lớp một rồi.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ là số đỉnh và số cạnh của đồ thị. ~(1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5)~

• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ thể hiện có cạnh từ đỉnh ~u~ tới đỉnh ~v~. ~(1 \le u, v \le 2 \times 10^5, u \neq v)~

Output

• Dòng đầu tiên chứa số nguyên ~k~ là số màu ít nhất cần dùng để giải bài toán của thầy giáo.

• ~m~ dòng tiếp theo, mỗi dòng chứa một số nguyên thể hiện màu được dùng để tô cạnh thứ ~i~ .

• Các màu khác nhau được đánh số lần lượt là ~1, 2, \ldots, k~ .

Subtask

• ~10\%~ số test có ~n \leq 7~.
• ~15\%~ số test không có cạnh nào của đồ thị thuộc quá ~1~ chu trình.
• ~15\%~ số test không có chu trình trong đồ thị.
• Các test còn lại không có điều kiện gì thêm.

Sample Input

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

Sample Output

2
1
2
2
2
2
2

Note

• Từ Sample Input, ta có đồ thị sau:

Copium là một vua trò chơi, với bất kể trò chơi nào trên đời thì anh ta luôn đứng ở vị trí thứ ~1~, chỉ cho đến khi illya xuất hiện. Ban đầu biết rằng sẽ rất khó để đánh bại anh trong các trò chơi có sẵn, illya quyết định tự nghĩ ra một trò chơi như sau: Cho một dãy các số nguyên dương từ ~1~ đến ~n~, illya sẽ chọn ra một cặp số là ~(a_1, a_2)~, Copium sẽ phải chọn ra một cặp số là ~(b_1, b_2)~. Vì là một người rất kĩ tính, để nắm chắc phần thắng thì illya cần đếm số trường hợp thỏa mãn :

• ~a_1, a_2, b_1, b_2~ là ~4~ số phân biệt nhau.
• ~a_1 \times a_2 > b_1 \times b_2~ .

Hãy giúp illya giành phần thắng trước Copium nhé!

Input

• Gồm một số nguyên duy nhất là ~n~ ~(4 \leq n \leq 10^7)~

Output

• Gòm một số nguyên duy nhất là số trường hợp thỏa mãn yêu cầu đề bài. Vì số trường hợp có thể rất nhiều nên hãy in ra đáp án với phần dư khi chia cho ~10^9 + 7~

Subtask

• Có ~30\%~ số test thỏa mãn ~1 \leq n \leq 2000~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.

Sample Input

4

Sample Output

3

Note

Ta có dãy ~{1, 2, 3, 4}~, sẽ có các trường hợp thỏa mãn sau đây:

• illya có cặp số ~{3, 4}~ và Copium có cặp số ~{1, 2}~, thỏa mãn ~3 \times 4 > 1 \times 2~. Vì vậy illya thắng.
• illya có cặp số ~{2, 4}~ và Copium có cặp số ~{1, 3}~, thỏa mãn ~2 \times 4 > 1 \times 3~. Vì vậy illya thắng.
• illya có cặp số ~{2, 3}~ và Copium có cặp số ~{1, 4}~, thỏa mãn ~2 \times 3 > 1 \times 4~. Vì vậy illya thắng.