Vinh đang tích cực chuẩn bị để tham gia vào kỳ thi Olympic Tin học Sinh viên Việt Nam, khối Siêu cúp. Khi xem lại đề thi của những kỳ thi gần đây, Vinh nhận thấy còn chưa có nhiều bài có liên quan đến việc áp dụng tìm kiếm nhị phân. Là người có nhiều kinh nghiệm từ các kỳ thi học sinh giỏi, Vinh nhanh chóng viết được đoạn mã cài đặt tìm kiếm nhị phân bằng ngôn ngữ C++ như sau:

int binary_search(vector<int> &a, int key) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mid = (l + r + 1) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] > key) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

Trong khi thực hiện kiểm thử chương trình, Vinh nhận thấy rằng dãy số đầu vào chưa được sắp xếp. Rất may vấn đề được phát hiện sớm và kịp thời xử lý. Tuy nhiên, trong đầu Vinh nảy ra một câu hỏi thú vị: "Có bao nhiêu hoán vị của các số nguyên từ ~1~ đến ~n~ mà hàm binary_search trả lại đúng chỉ số ~i~ sao cho ~a[i]=key~".

Hãy giúp Vinh giải quyết bài toán này. Vì đáp án có thể rất lớn, chỉ cần tìm số dư khi chia cho ~10^9+7~.

Input

Một dòng duy nhất gồm hai số nguyên ~n~ và ~key~ (~1\le key\le n\le 100000~) — độ dài và giá trị cần tìm đúng trong các hoán vị.

Output

Một số nguyên là đáp án của bài toán modulo ~10^9+7~.

Scoring

Sample Input 1

3 1

Sample Output 1

4

Sample Input 2

1 1

Sample Output 2

1

Cho ~P~ là một tập các điểm trên mặt phẳng. Ban đầu tập ~P~ rỗng. Có một dãy gồm ~n~ thao tác trên tập điểm này. Mỗi thao tác thuộc một trong hai dạng sau:

1. Thêm một điểm có toạ độ nguyên vào tập ~P~. Trong thao tác này điểm được thêm vào có hoành độ lớn hơn hẳn hoành độ các điểm hiện đang nằm trong ~P~.

2. Xoá khỏi ~P~ một số điểm có hoành độ lớn nhất.

Ta gọi bao lồi của tập ~P~ là đa giác lồi nhỏ nhất chứa tập ~P~. Nhiệm vụ của bạn là tính diện tích của bao lồi sau mỗi thao tác.

Input

Dòng đầu tiên gồm một số nguyên ~n~ (~n\le 10^5~) — số lượng thao tác.

Mỗi dòng trong ~n~ dòng tiếp theo gồm ba số nguyên ~t,x,y~ (~0\le t\le 1~, ~0\le x,y\le 2\cdot 10^9~). Gọi ~last,maxx,size~ lần lượt là hai lần diện tích bao lồi, hoành độ lớn nhất, kích thước của tập ~P~ trước khi thực hiện thao tác hiện tại. Ban đầu ~last = 0~ và nếu ~size=0~, ta coi ~maxx=-10^9~. Ta biến đổi ~t:=(t+last)\bmod 2~.

• Nếu ~t=0~, khi đó ta thực hiện thao tác ~1~, thêm điểm ~(x,y)~ vào tập sau khi biến đổi như sau:

  • ~x:=maxx+(last + x)\bmod (2\cdot 10^9+1)~

  • ~y:=(y+last)\bmod (2\cdot 10^9+1)-10^9~

  Dữ liệu đảm bảo ~|x|,|y|\le 10^9~ sau khi biến đổi.

• Nếu ~t=1~, ta thực hiện thao tác loại ~2~, xoá ~k~ điểm có hoành độ lớn nhất với ~k=(x+y+last) \bmod size + 1~.

  Dữ liệu đảm bảo ~size > 0~ khi thực hiện thao tác này.

Output

Sau mỗi thao tác, in ra hai lần diện tích bao lồi của tập ~P~ trên một dòng.

Scoring

Sample Input 1

6
0 1000000000 1000000000
0 1000000 1001000000
0 1000000 999000000
0 1001500 1000001500
1 85072946 2
1 61619603 2

Sample Output 1

0
0
3000000000000
6000000000000
3000000000000
0

Notes

Ta có kết quả sau khi biến đổi và kết quả thực hiện thao tác sau mỗi một trong ~6~ thao tác là:

1. ~t = 0, x = 0, y = 0~. Tập ~P = \{(0,0)\}~ nên hai lần diện tích bao lồi là ~0~.

2. ~t = 0, x = 10^6, y = 10^6~. Tập ~P = \{(0,0), (10^6, 10^6)\}~ nên hai lần diện tích bao lồi là ~0~.

3. ~t = 0, x = 2\cdot 10^6, y = -10^6~. Tập ~P = \{(0,0), (10^6, 10^6), (2\cdot 10^6, -10^6)\}~ nên hai lần diện tích bao lồi là ~3\cdot 10^{12}~.

4. ~t = 0, x = 3000000, y = 0~. Tập ~P = \{(0,0), (10^6, 10^6), (2\cdot 10^6, -10^6), (3\cdot 10^6, 0)\}~ nên hai lần diện tích của bao lồi là ~6\cdot 10^{12}~.

5. ~t = 1, k = 1~. Tập ~P = \{(0,0), (10^6, 10^6), (2\cdot 10^6, -10^6)\}~ nên hai lần diện tích bao lồi là ~3\cdot 10^{12}~.

6. ~t = 1, k = 2~. Tập ~P = \{(0,0)\}~ nên hai lần diện tích bao lồi là ~0~.

Tướng G được giao nhiệm vụ bảo vệ thành phố Alpha có dạng hình lục giác đều. Sau khi khảo sát địa thế và tìm chiến thuật để bảo vệ thành phố, Tướng G chia thành phố thành ~3n(n+1)+1~ khu vực có hình dạng ô tổ ong lục giác đều bằng nhau, phân bố đều xung quanh khu vực trung tâm. Các khu vực (các ô tổ ong) được đánh số ~1,2,3,\dots,3n(n+1)+1~ theo đường xoáy trôn ốc cùng chiều kim đồng hồ, bắt đầu từ khu vực trung tâm (xem minh họa với ~n=2~ ở hình ~1~). Một khu vực có thể có nhiều nhất ~6~ khu vực chung cạnh lân cận (xem minh họa ở hình ~2~). Tướng G đã cho đặt ~m~ bệ pháo giống hệt nhau ở ~m~ khu vực phân biệt có chỉ số ~p_1,p_2,\dots,p_m~ (~1 \leq p_1,p_2,\dots,p_m \leq 3n(n+1)+1~).

Tuy nhiên, sau khi nhận được những tin tức mới nhất từ quân báo về khả năng tấn công của địch, Tướng G quyết định thay đổi vị trí đặt các bệ pháo. Cụ thể, thay vì đặt các bệ pháo ở các khu vực ~p_1,p_2,\dots,p_m~, theo kế hoạch mới, chúng sẽ được đặt ở ~m~ khu vực phân biệt có chỉ số ~q_1,q_2,\dots,q_m~ (~1 \leq q_1,q_2,\dots,q_m \leq 3n(n+1)+1~). Để thực hiện việc di chuyển các bệ pháo sang các vị trí mới, Tướng G cần điều động các đội vận chuyển. Với mục đích giữ bí mật về các vị trí mới của các bệ pháo, mỗi đội vận chuyển được điều động chỉ thực hiện việc di chuyển bệ pháo từ một khu vực sang khu vực lân cận kề cạnh không có bệ pháo và sau khi hoàn thành nhiệm vụ này đội tự giải thể.

Cho biết danh sách ban đầu về các vị trí đặt các bệ pháo và danh sách mới về các vị trí đặt các bệ pháo, hãy giúp tướng G đưa ra phương án thực hiện việc di chuyển các bệ pháo đến các vị trí mới mà phải điều động ít đội vận chuyển nhất.

Input

Dòng thứ nhất gồm một số nguyên dương ~T~ ~(T\leq 5)~ là số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

Dòng đầu tiên của mỗi bộ dữ liệu gồm một số nguyên dương ~n~ và ~m~ (~n\le 50~, ~m < 3n(n+1)+1~).

Dòng thứ hai của mỗi bộ dữ liệu gồm ~m~ số nguyên dương ~p_1,p_2,\dots,p_m~ (~1 \leq p_1,p_2,\dots,p_m \leq 3n(n+1)+1~).

Dòng thứ ba của mỗi bộ dữ liệu gồm ~m~ số nguyên dương ~q_1,q_2,\dots,q_m~ (~1 \leq q_1,q_2,\dots,q_m \leq 3n(n+1)+1~).

Output

Với mỗi bộ dữ liệu, in ra một nhóm dòng theo khuôn dạng sau:

• Dòng đầu tiên ghi ra số nguyên không âm ~s~ là số lượng đội cần điều động để thực hiện việc di chuyển các bệ pháo;

• Tiếp đến là ~s~ dòng mô tả nhiệm vụ của ~s~ đội. Mỗi dòng ghi ~2~ số nguyên ~u, v~ cách nhau bởi dấu cách cho biết cần thực hiện việc di chuyển bệ pháo từ khu vực ~u~ sang khu vực ~v~.

  Nếu có nhiều phương án thực hiện thì chỉ cần đưa ra một cách bất kì.

Scoring

Sample Input 1

1
2 3
7 2 3
2 1 5

Sample Output 1

3
7 1
1 5
3 1

Notes

Tướng G cần điều động ít nhất ~3~ đội vận chuyển. Việc di chuyển ~3~ bệ pháo được đặt ở ba khu vực ~7, 2, 3~ sang ba vị trí mới được tiến hành như sau:

• Bệ pháo ở khu vực ~2~ giữ nguyên vị trí;

• Điều động một đội vận chuyển để di chuyển bệ pháo ở khu vực ~7~ sang khu vực ~1~. Tiếp đến, điều động một đội vận chuyển khác để di chuyển bệ pháo này sang khu vực ~5~.

• Cuối cùng, điều động một đội vận chuyển nữa để di chuyển bệ pháo đặt ở khu vực ~3~ sang khu vực ~1~.

Tộng cộng, theo phương án này cần điều động ~3~ đội vận chuyển.

Đây là một bài toán tương tác

Thi đấu với máy tính trong các trò chơi đối kháng luôn tạo ra nhiều cảm hứng cho người chơi. Lần này Hùng gặp phải một trò chơi hóc búa với máy tính sau đây.

Trò chơi diễn ra trên một đa giác lồi ~n~ đỉnh được đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ, trong đó người ta đã vẽ ~m~ đường chéo sao cho không có hai đường chéo nào cắt nhau ở trong đa giác và không có ~3~ đỉnh nào đôi một có đoạn nối (có thể là cạnh hoặc đường chéo của đa giác).

Hai đấu thủ luân phiên thực hiện nước đi. Đến lượt mình, người chơi phải vẽ thêm một đường chéo của đa giác sao cho đường chéo này không cắt bất cứ đường chéo nào đã vẽ trước đó tại điểm nằm trong đa giác và đồng thời không có bất cứ tam giác nào được tạo ra (nghĩa là không xuất hiện ~3~ đỉnh nào của đa giác đôi một có đoạn nối). Người đến lượt mà không có cách thực hiện được lượt đi là người thua cuộc và tất nhiên, đối thủ của anh ta là người giành phần thắng.

Hùng được quyền lựa chọn là người thực hiện nước đi trước hay sau, hãy giúp Hùng lựa chọn quyền thực hiện nước đi trước hay sau và thực hiện các lượt chơi để giành phần thắng.

Input

Dòng đầu tiên gồm hai số nguyên ~n, m~ (~n\le 100000~) — số đỉnh và số đường chéo đã nối sẵn của đa giác.

Mỗi dòng trong ~m~ dòng tiếp theo gồm hai số nguyên ~u,v~ thể hiện một đường chéo đã nối sẵn.

Interaction

Nếu bạn muốn Hùng đi trước, in ra "~0\ 0~".

Khi đến lượt của Hùng, nếu muốn nối đường chéo ~u-v~, in ra "~u\ v~".

Khi đến lượt của máy, đọc vào nước đi của máy dưới dạng "~x\ y~", máy sẽ nối đường chéo ~x-y~.

Nếu bạn thực hiện một nước đi không hợp lệ hoặc máy tính không thể thực hiện nước đi, chương trình sẽ dừng ngay lập tức.

Sau khi in ra một nước đi, đừng quên xuống dòng và flush đầu ra chuẩn, nếu không bạn có thể nhận verdict Time limit exceedded. Để làm điều này, bạn có thể 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 chuẩn đối với các ngôn ngữ khác.

Scoring

Sample Input 1

10 1
1 8

2 5

Sample Output 1

0 0

5 8