Bài tập

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.

Số tự nhiên \(p\) là số nguyên tố nếu \(p > 1\) và chỉ có 2 ước là \(1\) và \(p\).

Yêu cầu: Cho 2 số tự nhiên \(a\) và \(b\). Tính tổng các số nguyên tố và đếm số lượng số nguyên tố thuộc đoạn \([a, b]\).

Input

• Dòng đầu tiên ghi số nguyên dương \(T\) (\(T \le 10^6\));
• \(T\) dòng tiếp theo, mỗi dòng ghi 2 số tự nhiên \(a\) và \(b\) (\(0 < a \le b \le 10^6\)).

Output

Gồm \(T\) dòng, mỗi dòng ghi 2 số là tổng các số nguyên tố và số lượng số nguyên tố thuộc đoạn \([a, b]\) tương ứng.

Example

2
15 20
1 5

36 2
10 3

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm thỏa mãn: \(T = 1; \ a, b \le 10^3\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(T \le 10; \ a, b \le 10^5\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.