Cho dãy ~n~ số nguyên, số thứ ~i~ có giá trị là ~a_i~. Một thao tác nghịch đảo ~[x, y]~ sẽ đảo dấu toàn bộ các giá trị của các phần tử từ vị trí thứ ~x~ đến vị trí thứ ~y~ (số âm thành số dương, số dương thành số âm).

Yêu cầu: Cho ~q~ thao tác, hãy tính số lượng số dương, số lượng số âm của dãy số sau khi thực hiện ~q~ thao tác.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~1 \le n, q \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ mô tả giá trị của phần tử thứ ~i~ (~|a_i| \le 10^9~).
• ~q~ dòng sau, dòng thứ ~j~ chứa hai số nguyên ~x, y~ (~1 \le x \le y \le n~) mô tả thao tác.

Output

• Gồm một dòng duy nhất chứa hai số nguyên là số lượng số dương và số lượng số âm sau khi thực hiện ~q~ thao tác.

Sample Input 1

5 3
2 3 0 -1 4
1 4
2 5
1 5

Sample Output 1

3 1