Anh Thư và Việt An là đôi bạn tri kỉ đã cùng nhau lớn lên từ thời thơ ấu. Nhưng không biết từ khi nào, Anh Thư đã đem lòng thầm thương trộm nhớ cô bạn tri kỉ của mình. Vì không muốn mãi mãi làm bạn nên vào một ngày đẹp trời, Anh Thư đã ngỏ lời tỏ tình với Việt An.

Vì biết Anh Thư là một chàng trai thông minh nên Việt An không trả lời trực tiếp mà chỉ đưa cho Anh Thư một xâu ~S~ và một số ~k~ rồi nói rằng:

Nếu như từ xâu ~S~ có thể tạo thành xâu ~S'~ là xâu đối xứng bằng cách đổi vị trí các kí tự theo thứ tự bất kì trong phần tiền tố độ dài ~k~ của xâu ~S~ thì câu trả lời của Việt An sẽ là đồng ý. Ngược lại câu trả lời sẽ là không đồng ý.

Hãy giúp Anh Thư xác định câu trả lời của Việt An nhé.

Input

Dòng đầu nhập số nguyên dương ~T~ ~(T \le 10^5)~ là số testcase.

Với mỗi testcase:

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 10^6)~ là độ dài xâu ~S~ và số nguyên ~k~ ~(1 \le k \le \frac{n}{2})~

• Dòng thứ hai chứa xâu ~S~ chỉ gồm các kí tự là chữ cái Latin (từ a đến z) in thường.

Tổng độ dài xâu ~S~ trong tất cả testcase ~\le 10^6~.

Output

Với mỗi testcase, nếu câu trả lời của Việt An là đồng ý thì in ra Yes và xâu ~S'~. Ngược lại in No.

Sample Input 1

2
6 2
bacbca
6 3
bacbca

Sample Output 1

No
Yes
acbbca

DeMen100ns có một mảng ~a~ gồm ~n~ phần tử và được thực hiện thao tác sau đúng ~n - 1~ lần:

- ~x~ ~y~ : Chọn ~2~ phần tử có giá trị ~x~ và ~y~ ~(x \le y)~ trong mảng ~a~ sao cho vị trí trên mảng ~a~ của ~x~ và ~y~ là khác nhau. Xóa hai số ~x~ và ~y~ trong mảng ~a~ và thêm số ~k~ vào mảng ~a~ sao cho ~x \le k \le y~.

Sau ~n - 1~ thao tác thì mảng ~a~ chỉ còn đúng một phần tử, đây chính là kết quả ta cần tìm.

Các bạn hãy giúp DeMen100ns trả lời ~q~ truy vấn có dạng:

- ~x~: Có tồn tại cách thực hiện ~n - 1~ thao tác trên mảng ~a~ sao cho mảng ~a~ chỉ còn đúng một phần tử có giá trị là ~x~ hay không?

Input

• Dòng đầu tiên nhập ~2~ số ~n~ và ~q~ ~(n,\ q \le 10^5)~ là độ dài mảng ~a~ và số lượng truy vấn cần trả lời.

• Dòng thứ hai nhập ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

• ~q~ dòng tiếp theo, mỗi dòng nhập một số nguyên ~x~ ~(0 \le x \le 10^9)~ là dữ liệu cho truy vấn.

Output

In ra ~q~ dòng tương ứng với câu trả lời cho ~q~ truy vấn. Với mỗi truy vấn, nếu tồn tại cách thực hiện sao cho thỏa đề bài thì in ra Yes, ngược lại in ra No.

Subtask

• ~30\%~ số test có ~1 \le a_i \le 2~.

• Còn lại không có điều kiện gì thêm.

Sample Input 1

2 3
2 1
1
2
4

Sample Output 1

Yes
Yes
No

Sample Input 2

2 4
2 8
1
3
9
10

Sample Output 2

No
Yes
No
No

Notes

Ở ví dụ ~2~: DeMen100ns có thể thay thế ~2~ và ~8~ thành một trong các số ~2~, ~3~, ~4~, ~5~, ~6~, ~7~, ~8~.

Bạn là một chỉ huy cho một tiểu đội thuộc lực lượng đặc nhiệm Hoa Kỳ đang làm nhiệm vụ tại Afghanistan. Trong một lần đi làm nhiệm vụ, bạn bị phục kích bởi một lượng lớn phiến quân Taliban, mặc dù đã ra sức bắn trả nhưng hoả lực của kẻ thù là rất lớn. Trong tình huống đó bạn đã quyết định gọi sự hỗ trợ từ không quân. Ngay lập tức, căn cứ đã cử đi chiếc phi cơ ném bom AC-130 để giúp đỡ, tuy nhiên, việc phải bắn trả từ trên cao là rất khó và số lượng đạn dược hiện tại là không nhiều nên bạn cần phải định vị vị trí của quân địch cho phi công.

Được biết hiện tại có ~N~ quân địch ở các vị trí ~(x, y)~ trên bản đồ. Bạn cần phải tìm một tập hợp S không rỗng gồm các vị trí ~i~ là các địa điểm để tấn công. Độ hiệu quả của một chiến dịch tấn công được tính bằng giá trị ~F~ = ~\sum_{i \in S}y_i - (max(x_i) - min(x_i))~. Hãy tìm chiến dịch tấn công có độ hiệu quả lớn nhất để giúp các đồng đội và bảo toàn cái mạng nhỏ của bạn quay về.

Input

• Dòng đầu tiên gồm số ~N~ là số lượng phiến quân Taliban ~(2 \le N \le 5 \times 10^5)~

• ~N~ dòng sau mỗi dòng gồm ~2~ số ~x_i~, ~y_i~ chỉ toạ độ của tên lính thứ ~i~ ~(1 \le x_i \le 10^{15}, 1 \le y_i \le 10^9)~

Output

• Một số nguyên duy nhất là độ hiệu quả ~F~ lớn nhất của chiến dịch tấn công tìm được.

Subtask

• ~10\%~ số test đầu tiên có ~N \le 20~

• ~20\%~ số test tiếp theo có ~N \le 300~

• ~20\%~ số test tiếp theo có ~N \le 5000~

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

Sample Input 1

3
2 3
10 2
4 5

Sample Output 1

6

Note

• Chọn điểm ~1~ và ~3~ để có ~(3 + 5) - (4 - 2) = 6~.

ngpin04 là một nhà thám hiểm địa chất nổi tiếng. Một hôm, ngpin04 thám hiểm trong hang và gặp được một bài toán rất hay được khắc trên một tảng đá như sau:

Cho số nguyên dương ~n~ ~(n \leq 10^{12})~. Hãy tìm tất cả cặp số nguyên dương ~(x,y)~ (~x\le y~) sao cho ước chung lớn nhất và bội chung nhỏ nhất của hai số đó lần lượt là ~n~ và ~n^2~, sau đó tính tổng các ~x+y~. Nói cách khác cần tính tổng ~\displaystyle \sum_{x\le y,gcd(x,y)=n,lcm(x,y)=n^2}x+y~.

Tuy là một nhà thám hiểm địa chất nhưng ngpin04 rất đam mê toán học, bạn hãy giúp cậu ấy giải bài toán này nhé!

Trong đó:

• Ước chung lớn nhất (ƯCLN) của hai số nguyên là số nguyên dương lớn nhất là ước số chung của hai số đó.
• Bội chung nhỏ nhất (BCNN) của hai số nguyên là số nguyên dương nhỏ nhất chia hết cho cả hai số đó.

Input

Dòng đầu tiên gồm số nguyên ~t~ ~(1 \leq t \leq 10)~ là số bộ test.

~t~ dòng tiếp theo mỗi dòng gồm 1 số nguyên ~n~ ~(1 \leq n \leq 10^{12})~.

Output

Với mỗi bộ test, in ra một số nguyên duy nhất là tổng cần tính trên một dòng, chia lấy dư cho ~10^9+7~.

Subtask

• ~40\%~ số test có ~n \leq 10^3~.

• ~30\%~ số test có ~n \leq 10^{6}~.

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

Sample Input 1

3
2
3
4

Sample Output 1

6
12
20

Ba bé Naot, lastPledge và LeThanhMinh cùng tham gia một trò chơi mang tên "Ba chàng lính ngự lâm". Trò chơi được diễn ra trên bảng ~N\times M~, ba bé sẽ chọn ba ô khác nhau trên bảng sao cho không có người nào có thể đi đến vị trí của người khác bằng một bước di chuyển theo hướng của quân mã trong cờ vua. Hãy đếm số trạng thái khác nhau của trò chơi (hai trạng thái được gọi là khác nhau nếu có ít nhất một người đứng ở hai vị trí khác nhau trong hai trạng thái đó).

Input

Dòng đầu tiên chứa một số nguyên dương ~T~ là số bộ test (~T\le 10000~).

~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~N~ và ~M~ (~1 \le N, M \le 10^{9}~) ứng với một bộ test.

Output

Với mỗi truy vấn in ra số trạng thái khác nhau chia lấy dư cho ~10 ^ {9} + 7~.

Subtask

• ~20\%~ số test có ~T\le 10, 1\le N * M \le 1000~.

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

Sample Input 1

2
2 3
5 4

Sample Output 1

72
3732