Tỉnh Thái Nguyên có n có n điểm tham quan được đánh số từ 1 tới n, điểm tham quan thứ i có toạ độ (\(x_i,y_i\)), được kết nối với nhau bằng những con đường một chiều. Vì địa hình đặc thù nên chính phủ chỉ xây đường đi từ điểm tham quan thứ i tới điểm tham quan thứ j nếu như \(x_i > x_j\) và \(y_i < y_j\). An muốn tham qua một số địa điểm, để chuẩn bị kĩ lưỡng cho chuyến đi, cậu muốn tìm hiểu xem với mỗi số nguyên dương \(l\) (\(1 \leq l \leq n\)), có bao nhiêu hành trình tham quan đi theo những đường đi có sẵn mà đi qua đúng l điểm tham quan. Các bạn lập trình viên hãy giúp An nghiên cứu vấn đề này nhé. Lấy kết quả theo modulo \(10^9 + 7\).

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương n \((1 \leq n \leq 2000)\) - số điểm tham quan.
• Dòng thứ hai chứa n số nguyên \(x_1,x_2,...,x_n\) (\(0 \leq |x_i| \leq 10^9\)) là hoành độ của các điểm tham quan.
• Dòng thứ ba chứa n số nguyên \(y_1, y_2,...,y_n\) (\(0 \leq |y_i| \leq 10^9\)) là tung độ của các điểm tham quan.

Kết quả:

• Ghi một dòng gồm n số nguyên không âm, số thứ i là số hành trình đi qua đúng I điểm tham quan, tính theo modulo \(10^9 + 7\)

Input:

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

Ouput:

6 7 3 0 0 0

Giải thích

• Các hành trình gồm 1 điểm tham quan: (1); (2); (3); (4); (5); (6).
• Các hành trình gồm 2 điểm tham quan: (4, 1); (4, 2); (4, 6); (5, 1); (5, 2); (5, 4); (5, 6).
• Các hành trình gồm 3 điểm tham quan: (5, 4, 2); (5, 4, 6); (5, 4, 1).
• Không có hành trình thoả mãn đi qua 4, 5 hoặc 6 điểm tham quan.

Ràng buộc:

• Có 20% số điểm thỏa mãn: n ≤ 10;
• Có 20% số điểm thỏa mãn: n ≤ 500;
• Có 60% số điểm không có ràng buộc gì thêm.