Bài tập

Hoành Sơn là một địa điểm du lịch nổi tiếng trên toàn thế giới bởi sự hùng vĩ cũng như sự đa dạng phong phú về các dãy núi và những cây cầu bắc qua. Địa điểm du lịch Hoành Sơn có các dịch vụ tham quan theo yêu cầu. Cụ thể là bạn chỉ việc đưa ra yêu cầu lộ trình, sau đó dịch vụ sẽ tính toán và đưa bạn đi qua các cây cầu và ngọn núi theo đúng yêu cầu về lộ trình.

Địa điểm du lịch ở đây có \(N\) ngọn núi và \(M\) cây cầu, mỗi cây cầu nối hai ngọn núi nào đó với nhau. Giữa hai ngọn núi bất kì có thể có nhiều cây cầu nối hai ngọn núi đó với nhau. Cũng có thể có những ngọn núi có những cây cầu tự nối với chính nó tạo ra hình vòng cung để những khách du lịch có thể đứng xung quanh ngọn núi tham quan và chụp ảnh. Hiểu đơn giản thì mô hình của khu du lịch là một đa đồ thị vô hướng \(N\) đỉnh \(M\) cạnh.

Các ngọn núi được đánh số từ 1 đến \(N\) và ngọn núi thứ \(i\) có độ cao là \(A_i\). Về độ dốc của các cây cầu thì nó được tính theo chênh lệch chiều cao của hai ngọn núi ở hai đầu cây cầu. Nói cách khác, nếu cây cầu nối hai ngọn núi \(x\) và \(y\) thì độ dốc của nó là \(|A_x - A_y|\).

Sau khi đạt giải quốc gia, Tuấn muốn tự thưởng cho mình chuyến du lịch đến Hoành Sơn sau cả năm trời ôn luyện vất vả và chuẩn bị bước vào đại học. Đến Hoành Sơn, Tuấn muốn thiết kế một hành trình "lên đỉnh siêu dốc", xuất phát từ một ngọn núi nào đó, đi đến các ngọn núi khác với điều kiện ngọn núi sau cao hơn ngọn núi trước, không những thế, độ dốc của cây cầu sau cũng phải lớn hơn độ dốc của cây cầu trước đó. Nghĩa là, nếu như Tuấn quyết định chọn một hành trình đi qua các ngọn núi theo thứ tự \(P_1, P_2, \ldots, P_k\) thì hành trình đó sẽ phải thỏa mãn tính chất:

Yêu cầu: Hãy giúp hướng dẫn viên du lịch cho Tuấn hành trình "lên đỉnh siêu dốc" qua nhiều đỉnh núi nhất và trả lời thắc mắc của Tuấn là có bao nhiêu hành trình khác nhau đạt được nhiều đỉnh núi nhất như vậy. Hai hành trình gọi là khác nhau nếu tồn tại một cây cầu hành trình này có mà hành trình kia không hoặc ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((1 \leq N \leq 3 \times 10^5,\ 1 \leq M \leq 5 \times 10^5)\).
• Dòng thứ hai chứa độ cao của \(N\) ngọn núi là \(N\) số nguyên dương \(A_1, A_2, ..., A_n\) \((1 \leq A_i \leq 10^9)\).
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa cặp số nguyên dương \((U_i, V_i)\) là chỉ số hai ngọn núi là hai đầu của cây cầu thứ \(i\) \((1 \leq U_i, V_i \leq N)\).

Output

In ra kết quả trên 2 dòng:

• Dòng đầu tiên ghi ra một số nguyên là số lượng đỉnh núi của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng lộ trình khác nhau tìm được cho \(10^9 + 7\).

Example

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

3
1

Scoring

• Có 22% số test ứng với \(N \leq 20\).
• Có 28% số test khác ứng với \(N \leq 500\).
• Có 20% số test khác ứng với \(M = N - 1\), và các đỉnh trong đồ thị liên thông với nhau.
• 30% còn lại không có giới hạn gì thêm.

3M là một học sinh chuyên Văn nhưng cô ấy rất ham mê tìm hiểu các cấu trúc dữ liệu.
Hôm nay cô ấy được thầy Nhật dạy về cấu trúc dữ liệu deque, thứ có thể giúp bạn
thêm bớt ở cả hai đầu của một dãy số. Sau khi học xong, 3M đã nghĩ ra một bài toán
truy vấn rất hấp dẫn và tự đặt ra cho mình câu hỏi: "Liệu bài này có thể làm bằng deque
hay không?".

Bài toán được mô tả như sau: Cho dãy số gồm \(n\) phần tử và có \(q\) truy vấn thuộc một
trong hai dạng sau:

• POFPUB x: Lấy phần tử đầu tiên của dãy và thêm nó vào cuối dãy. Lặp lại
  thao tác đó \(x\) lần (\(1 \le x \le 10^{9}\)).
• SUM l r: Tính tổng các phần tử nằm trên đoạn \([l, r]\) (\(1 \le l \le r \le n\)).

Input

Nhập từ file DEQUE.INP:

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\) (\(1 \le n \le 10^{6},\ 1 \le q \le 10^{6}\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng đã nêu.

Output

Ghi ra file DEQUE.OUT:

• Với mỗi truy vấn SUM l r, in ra tổng các phần tử trong đoạn \([l, r]\).

Example

5 5
2 3 2 4 5
POFPUB 2
SUM 3 5
POFPUB 2
SUM 3 5
SUM 1 5

10
9
16

3 3
1 1 1
POFPUB 17
SUM 1 2
SUM 1 3

2
3

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm: \(1 \le n, q \le 1000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm: \(a_1 = a_2 = \cdots = a_n\).
• \(10\%\) số test tương ứng với \(10\%\) số điểm: với mọi truy vấn SUM, ta có \(l = 1, r = n\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại: không có ràng buộc gì thêm.

Rin có một cây gồm \(n\) đỉnh. Các đỉnh của cây được đánh số từ \(1\) đến \(n\). Ban đầu tất cả các đỉnh được sơn màu xanh.

Khoảng cách giữa hai đỉnh \(u\) và \(v\) trên cây là số cạnh trên đường đi ngắn nhất giữa \(u\) và \(v\).

Rin muốn thực hiện nhanh chóng các truy vấn thuộc hai loại sau:

• Đổi màu một đỉnh của cây, nếu đỉnh đang được sơn màu xanh thì ta sơn lại nó bằng màu đỏ và ngược lại;

• Tính xem nút màu đỏ nào gần nút nhất đã cho và in ra khoảng cách ngắn nhất đến nút màu đỏ gần nhất.

Nhiệm vụ của bạn là viết một chương trình để giúp Rin thực hiện các truy vấn trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((2 \leq n \leq 10^5, 1 \leq m \leq 10^5)\) - số nút trong cây và số truy vấn.

• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) \((1 \leq u, v \leq n, u \neq v)\) thể hiện một cạnh của cây..

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(t\) \((1 \leq t \leq 2)\) và \(v\) \((1 \leq v \leq n)\) thể hiện \(1\) truy vấn. Nếu \(t = 1\), nếu đỉnh \(v\) được sơn màu xanh thì ta sơn lại nó bằng màu đỏ và ngược lại . Nếu \(t = 2\), in ra khoảng cách ngắn nhất từ đỉnh \(v\) đến một đỉnh được sơn màu đỏ, nếu không có đỉnh nào được sơn màu đỏ thì câu trả lời là \(-1\).

Output

Đối với mỗi truy vấn có \(t = 2\), bạn hãy in ra đáp án của truy vấn trên \(1\) dòng duy nhất.

Example

5 8
1 2
2 3
2 4
4 5
1 1
2 1
2 5
1 2
2 5
1 1
1 2
2 1

0
3
2
-1

Scoring

• Subtask 1 (18 điểm) : \(1 \leq n, q \leq 5000\)

• Subtask 2 (32 điểm): Số đỉnh được sơn màu đỏ tại mỗi thời điểm không quá \(500\)

• Subtask 3 (50 điểm): Không có rằng buộc gì thêm

Loại xe điện Alset mới được nghiên cứu bởi giáo sư Q của trường đại học LQD được đánh giá cao trong giới chuyên môn, và sẽ sớm được đưa ra thị trường. Nhằm đánh giá kĩ hơn các đặc tính của xe, các nhà đầu tư muốn theo dõi giáo sư Y mô phỏng quá trình vận hành của nó.
Trong điều kiện mô phỏng, bản đồ thành phố được đơn giản hóa thành lưới ô vuông vô tận. Ta gắn vào bản đồ này một hệ trục tọa độ Oxy. Giả sử có giao lộ nằm tại mọi điểm có tọa độ nguyên của mặt phẳng; và với mọi giao lộ \((x, y)\), luôn có con đường nối:

• Giao lộ tại \((x, y)\) với giao lộ tại \((x, y + 1)\).
• Giao lộ tại \((x, y)\) với giao lộ tại \((x + 1, y)\).

Xe điện Alset chỉ có thể đi dọc theo các con đường, đi từ một giao lộ này tới giao lộ khác liền kề nó. Trong một đơn vị thời gian, sử dụng một đơn vị năng lượng tiêu chuẩn, xe có thể đi từ giao lộ \((x, y)\) tới giao lộ \((u, v)\) nếu \(|x - u| + |y - v| = 1\).

Người ta cũng bố trí \(n\) trạm sạc đặc biệt, trạm thứ \(i\) ở tại giao lộ \((x_{i}, y_{i})\). Mỗi khi dừng tại một trong những trạm này, xe sẽ được nạp đầy năng lượng, bằng với dung tích \(w\) của nó.

Trong mô phỏng này, có \(q\) thử thách được đặt ra. Thử thách thứ \(j\) giả sử rằng nếu xe bắt đầu tại trạm sạc thứ \(s_{j}\), để đi tới được trạm thứ \(t_{j}\), thì dung tích \(w\) của nó nhỏ nhất có thể bằng bao nhiêu? (trong quá trình di chuyển có thể đi qua các trạm sạc khác tùy ý).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\) lần lượt là số trạm sạc và số thử thách.

• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((|x_{i}|, |y_{i}| \leq 10^{9})\) là vị trí của trạm sạc thứ \(i\).

• Trong \(q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(s_{j}\) và \(t_{j}\) \((1 \leq s_{j}, t_{j} \leq n)\) mô tả một thử thách thứ \(j\).

Output

• Gồm \(q\) dòng, dòng thứ \(j\) chứa đáp án của thử thách thứ \(j\).

Example

5 3
0 0
0 0
3 3
1 2
6 8
1 2
2 3
1 5

0
3
8

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 100\).

• Subtask \(2\) (\(20\%\) số điểm): \(n, q \leq 1000\).

• Subtask \(3\) (\(20\%\) số điểm): \(x_{i} = 0\) với mọi \(1 \leq i \leq n\).

• Subtask \(4\) (\(20\%\) số điểm): \(0 \leq x_{i} \leq 1\) với mọi \(1 \leq i \leq n\).

• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.