Nhân dịp kết thúc năm học, Bảo Bay Bổng và gia đình sẽ đi du lịch tại đất nước A. Cậu được bố mẹ giao cho công việc lên kế hoạch cho chuyến đi.

Đất nước A 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 ~(i,j)~ 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~. Để 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 \le l \le 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.

Hãy giúp Bảo Bay Bổng nghiên cứu vấn đề này. Lấy kết quả theo modulo ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2000)~ - số điểm tham quan.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, ... , x_n~ ~(0 \le |x_i| \le 10^9)~ - 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 \le |y_i| \le 10^9)~ - tung độ của các điểm tham quan.

Output

• In ra trên một dòng là ~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~.

Samples

Sample Input 1

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

Sample Output 1

6 7 3 0 0 0

Clarification

• 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.

Scoring

• Subtask ~1~ (~20\%~ số test): ~n \le 10~
• Subtask ~2~ (~20\%~ số test): ~n \le 500~
• Subtask ~3~ (~60\%~ số test): Không có ràng buộc gì thêm