Thi thử VOI ngày 1

Bài 1. Mê cung

Một mê cung được biểu diễn bằng một bảng vuông \(A\) kích thước \(n \times n\) ô, các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải, ô nằm giao giữa hàng \(i\) và cột \(j\) được gọi là ô \((i, j)\). Một số ô của bảng có chướng ngại vật và được đánh dấu là \(1\), những ô còn lại là các ô trống và được đánh dấu \(0\). Một robot chỉ di chuyển trong bảng và có thể đi từ ô trống này sang ô trống khác lân cận kề cạnh. Một đường đi của robot giữa hai ô trống là một dãy các ô lân cận từ ô này tới ô kia và không có ô nào đi qua quá một lần, độ dài của đường đi được tính bằng số lượng ô mà robot đi qua. Bảng \(A\) là mê cung nên giữa hai ô trống bất kỳ của bảng có đúng một đường đi giữa chúng.

Hãy xử lí \(q\) thao tác, mỗi thao tác thuộc một trong hai dạng sau:

• Thao tác dạng: 1 u v, thao tác này sẽ thực hiện đặt chướng ngại vật vào ô \((u, v)\). Chú ý rằng, sau khi thực hiện thao tác loại này, bảng \(A\) có thể không còn là mê cung nữa;
• Thao tác dạng: 2 u v x y, thao tác này cần tính độ dài đường đi từ ô \((u, v)\) đến ô \((x, y)\). Nếu không tồn tại đường đi đưa ra -1.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\);
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa xâu \(n\) ký tự {0, 1} mô tả hàng thứ \(i\) của \(A\);
• Dòng thứ \(j\) trong \(q\) dòng tiếp theo mô tả thao tác thứ \(j\).

Output

• Gồm một số dòng tương ứng là các câu trả lời cho thao tác tìm độ dài đường đi giữa hai ô.

Example

3 2
000
110
000
2 1 1 3 1
1 2 3
2 1 1 3 1

7
-1

Subtask

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\); \(q \le 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 1000\); \(q \le 10^5\) và chỉ có thao tác loại \(2\);
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 1000\); \(q \le 10^5\).

Dãy con của một dãy là dãy thu được bằng cách xoá đi một số phần tử của dãy ban đầu (có thể không xoá phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng một trong hai dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên \(a\) có \(n\) phần tử, hãy đếm số dãy con của \(a\) là dãy tăng kép.

Input

• Dòng đầu tiên chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)).

Output

• In ra số lượng dãy tăng kép là dãy con của \(a\), sau khi chia lấy dư cho \(1000000007\).

Example

4
3 3 4 2

9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 200\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 2000\) và \(a_i \le 200\).
• Subtask \(4\) (\(35\%\) số điểm): \(n \le 2000\).

Cho \(1\) cây \(n\) đỉnh và \(1\) tập \(A\) gồm \(m\) đỉnh trên cây. Khoảng cách giữa \(2\) đỉnh trên cây là số cạnh trên đường đi giữa \(2\) đỉnh đó. Người ta thực hiện \(q\) thao tác thuộc \(1\) trong \(2\) loại sau:

• 1 u: nếu đỉnh \(u\) chưa có trong tập \(A\) thì thêm đỉnh \(u\) vào tập \(A\), ngược lại nếu đỉnh \(u\) có trong tập \(A\) thì bỏ đỉnh \(u\) ra khỏi tập \(A\).
• 2 u: gọi \(h\) là khoảng cách tối thiểu từ \(1\) đỉnh trong tập \(A\) tới \(u\), tìm \(h\) và đếm số đỉnh trong tập \(A\) có khoảng cách tới \(u\) bằng \(h\).

Input

• Dòng đầu tiên chứa \(3\) số nguyên dương \(n, m, q\).
• \(n - 1\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(u, v\) tương ứng với có cạnh nối từ \(u\) đến \(v\) trên cây.
• Dòng tiếp theo chứa \(m\) số nguyên phân biệt là các đỉnh thuộc tập \(A\).
• \(q\) dòng tiếp theo, mỗi dòng chứa \(1\) trong \(2\) loại truy vấn.

Output

• Với mỗi truy vấn loại \(2\) in ra \(2\) số nguyên lần lượt là khoảng cách tối thiểu cần tìm và số đỉnh trong tập \(A\) có khoảng cách đó. Dữ liệu đảm bảo lúc này tập \(A\) luôn có ít nhất \(1\) phần tử.

Example

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

0 1
2 2
5 2

Subtask

• Subtask \(1\) (\(25\%\) số điểm): \(1 \leq n, q \leq 5000\)
• Subtask \(2\) (\(25\%\) số điểm): \(1 \leq n, q \leq 30000\) và không có thao tác loại \(1\)
• Subtask \(3\) (\(25\%\) số điểm): \(1 \leq n, q \leq 30000\)
• Subtask \(4\) (\(25\%\) số điểm): \(1 \leq n, q \leq 50000\)