Bài tập

Bạn được cho một cây có \(n\) đỉnh. Mỗi đỉnh trên cây được gán một ký tự là một dấu ngoặc đơn, có thể là ( hoặc ).

Một đường đi đơn giữa hai đỉnh \(u\) và \(v\) tạo ra một chuỗi ngoặc bằng cách ghép các ký tự ngoặc của các đỉnh trên đường đi theo thứ tự. Chuỗi ngoặc này được coi là hợp lệ nếu:

• Tổng số dấu ngoặc mở bằng tổng số dấu ngoặc đóng.
• Với bất kỳ tiền tố nào của chuỗi, số dấu ngoặc mở không nhỏ hơn số dấu ngoặc đóng.

Hãy tìm và đếm số cặp đỉnh \((u, v)\) (với \(u\) và \(v\) là hai đỉnh bất kỳ trên cây) sao cho chuỗi ngoặc được tạo từ đường đi giữa chúng là một chuỗi ngoặc hợp lệ.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 3 \cdot 10^5\)), là số đỉnh của cây.
• Dòng thứ hai chứa \(n\) ký tự \(s_1, s_2, \ldots, s_n\) (\(s_i \in \{'(', ')'\}\)), trong đó \(s_i\) là ký tự ngoặc tại đỉnh thứ \(i\).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n, u \ne v\)), biểu thị một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

In ra một số nguyên duy nhất là tổng số cặp đỉnh \((u, v)\) thỏa mãn yêu cầu.

Example

6
()()()
1 2
2 3
3 4
3 5
5 6

5

Scoring

• Subtask 1 (30 điểm): \(2 \le n \le 5000\).
• Subtask 2 (70 điểm): Không có ràng buộc bổ sung.

Ngày xửa ngày xưa, trong vương quốc Kỳ Diệu, nhà vua tổ chức một cuộc thi dành cho những chiến binh dũng cảm và thông minh nhất. Nhà vua giao cho các chiến binh một danh sách gồm \(N\) nhiệm vụ để thực hiện, mỗi nhiệm vụ chỉ được hoàn thành khi chiến binh bắt đầu tác vụ từ thời điểm \(l_i\) và hoàn thành tại thời điểm \(r_i\).

Vì độ khó của các nhiệm vụ, các chiến binh không thể đồng thời thực hiện nhiều tác vụ cùng một thời điểm, hay cụ thể là hai nhiệm vụ giao nhau. Hai nhiệm vụ \([l_i, r_i]\) và \([l_j, r_j]\) được gọi là giao nhau nếu tồn tại một thời điểm thuộc cả \(2\) nhiệm vụ trên.

Cuộc thi trên không chỉ là cơ hội tìm kiếm chiến binh mạnh nhất, mà còn là cơ hội để những người "mạnh" về trí não thể hiện khả năng. Cụ thể, nhà vua giao ra bài toán sau, nếu một chiến binh chỉ được làm các nhiệm vụ trong khoảng thời gian từ \(S\) đến \(T\) thì họ có thể hoàn thành tối đa bao nhiêu nhiệm vụ. Nhận thấy bài toán chưa đủ hóc búa, nhà vua bèn chèn thêm một số cập nhật giữa các câu hỏi: thay đổi thời gian của nhiệm vụ \(i\) thành \(U_i\) đến \(V_i\).

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), là số lượng nhiệm vụ.

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\) và \(r_i\) \((1 \leq l_i \le r_i \leq 10^9)\), biểu diễn thời gian bắt đầu và kết thúc của nhiệm vụ thứ \(i\).

• Dòng tiếp theo chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)), là số lượng yêu cầu mà nhà vua đưa ra.

• Q dòng tiếp theo thuộc một trong \(2\) loại:
  \begin itemize

• \(1 \; i \; u \; v\): Gán \(l_i=u\) và \(r_i=v\).
• \(2 \; S \; T\): Nếu chỉ được phép làm nhiệm vụ trong khoảng thời gian \([S, T]\), thì một chiến binh có thể làm nhiều nhất bao nhiêu nhiệm vụ.
  \end itemize

Output

Xử lý các yêu cầu và đưa ra đáp án cho các câu hỏi của nhà vua.

Example

5
1 5
3 7
2 4
7 10
6 11
4
2 3 10
2 2 10
1 2 11 13
2 1 14

1
2
3

Scoring

Trong tất cả các test:

\(1 \le u \le v \le 10^9\)

\(1 \le S \le T \le 10^9\)

\textbf Cách tính điểm:
\begin itemize

• Có \(15\%\) số điểm ứng với \(n, q \le 20\).
• Có \(15\%\) số điểm ứng với \(n, q \le 10^3\).
• Có \(20\%\) số điểm ứng với \(l_i = r_i\) và \(u = v\).
• Có \(20\%\) số điểm với bộ test không có truy vấn loại \(1\).
• \(30\%\) điểm còn lại không có ràng buộc gì thêm.
  \end itemize

Putata đang chơi một trò chơi rắn nổi tiếng trên máy tính xách tay của mình, trong đó con rắn di chuyển trên một bàn cờ kích thước \(n \times m\). Trên bàn cờ này có thể có một số ô chứa chướng ngại vật. Con rắn có thể được biểu diễn như một dãy các cặp tọa độ xác định vị trí của thân nó: \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\). Ở đây, \(k\) là độ dài của con rắn. Đầu của con rắn là tại \((x_1, y_1)\), đuôi là tại \((x_k, y_k)\), và các phần thân liền kề sẽ nằm trên các ô liền kề nhau theo cạnh.

Trong trò chơi này, con rắn sẽ được điều khiển bằng một chuỗi các lệnh di chuyển. Có 5 loại lệnh mà bạn có thể sử dụng:

• L: Di chuyển con rắn một ô sang trái. Đầu của con rắn sẽ di chuyển tới \((x_1, y_1 - 1)\).
• R: Di chuyển con rắn một ô sang phải. Đầu của con rắn sẽ di chuyển tới \((x_1, y_1 + 1)\).
• U: Di chuyển con rắn một ô lên trên. Đầu của con rắn sẽ di chuyển tới \((x_1 - 1, y_1)\).
• D: Di chuyển con rắn một ô xuống dưới. Đầu của con rắn sẽ di chuyển tới \((x_1 + 1, y_1)\).
• S: Rút ngắn chiều dài của con rắn đi một đơn vị. Đuôi của con rắn sẽ bị xóa đi, độ dài của con rắn sẽ trở thành \(k - 1\). Lưu ý rằng bạn không thể thực hiện lệnh này khi \(k = 1\).

Khi đầu của con rắn di chuyển, mỗi phần thân của nó cũng sẽ di chuyển theo. Cụ thể, phần thân thứ \(i\) \((2 \leq i \leq k)\) sẽ di chuyển đến vị trí mà phần thân thứ \((i-1)\) ở đó trước khi lệnh được thực hiện. Con rắn không thể di chuyển vào một ô có chướng ngại vật, và không thể di chuyển ra ngoài bàn cờ. Ngoài ra, con rắn không được tự va vào thân của nó, nghĩa là không được có hai phần của thân nằm trên cùng một vị trí.

Trường hợp đặc biệt

Xem xét trường hợp đặc biệt sau: Đầu của con rắn ở vị trí \((x_1, y_1)\), và đuôi ở vị trí \((x_k, y_k)\). Nếu đầu của con rắn đang di chuyển đến \((x'_1, y'_1) = (x_k, y_k)\), thì được phép hoán đổi vị trí đầu và đuôi của con rắn bằng một lệnh duy nhất khi \(k = 2\).

Yêu cầu

Bạn sẽ được cung cấp bản đồ của bàn cờ và vị trí của thân con rắn. Gọi \(f(i, j)\) là số lệnh tối thiểu để đầu của con rắn có thể đến vị trí \((i, j)\), hoặc \(0\) nếu không thể. Nhiệm vụ của bạn là tính giá trị sau:

$
\left( \sum_{i=1}^n \sum_{j=1}^m f(i, j)^2 \right) \mod 2^{32}.
$

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\) \((1 \leq n, m \leq 3000, 1 \leq k \leq \min\{nm, 10^5\})\) - kích thước của bàn cờ và độ dài của con rắn.
• Trong \(k\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) \((1 \leq x_i \leq n, 1 \leq y_i \leq m, |x_i - x_{i+1}| + |y_i - y_{i+1}| = 1)\) biểu thị vị trí của phần thân thứ \(i\) của con rắn. Đảm bảo rằng tất cả các cặp tọa độ \((x_i, y_i)\) là khác nhau và không có phần thân nào nằm trên ô chứa chướng ngại vật.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa một chuỗi có độ dài \(m\). Nếu ô \((i, j)\) trống, ký tự thứ \(j\) trong dòng thứ \(i\) là '.'. Nếu ô \((i, j)\) chứa chướng ngại vật, ký tự đó là '#'.

Output

In ra một số nguyên không âm là đáp án cho bài toán.

Example

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

293

2 2 4
1 1
1 2
2 2
2 1
..
..

14

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

407

Scoring

• Có \(25\%\) số test có \(n, m, k \leq 5\).

• Có \(25\%\) số test có \(k = 2\).

• Có \(25\%\) số test có \(n, m \leq 300\), \(2 < k \leq 5\).

• \(25\%\) số test còn lại không có ràng buộc gì thêm.

Bạn đang khám phá một tòa nhà lớn gồm \(R\) hàng và \(C\) cột phòng, tạo thành một lưới ô vuông kích thước \(R \times C\). Ô ở góc trái trên là ô \((1,1)\) và ô ở góc phải dưới là \((R,C)\).

Mỗi căn phòng của tòa nhà này có một mức độ bảo vệ \(A_{i,j}\) và trong mỗi phòng có chứa một gói kẹo loại \(B_{i,j}\). Bạn sẽ bắt đầu tại một căn phòng \((x, y)\) và chỉ được phép đi qua các phòng có mức độ bảo vệ không vượt quá \(k\) thì số loại kẹo khác nhau lớn nhất bạn thu thập được là bao nhiêu.

Lưu ý rằng bạn chỉ có thể di chuyển sang các phòng kề nhau theo bốn hướng: trái, phải, trên, dưới.

Không dừng lại ở đó, tòa nhà này lại thay đổi theo thời gian, nghĩa là sẽ có thời điểm loại kẹo tại một phòng bị thay đổi. Xen giữa những lần thay đổi này, bạn được yêu cầu trả lời các câu hỏi có dạng \((x,y,a)\) như trên.

Bạn cần xử lý \(Q\) truy vấn sau:

• 1 \(x\) \(y\) \(b\) --- loại kẹo tại hàng \(x\), cột \(y\) được thay đổi thành \(b\).
• 2 \(x\) \(y\) \(a\) --- nếu bắt đầu từ phòng \((x, y)\), chỉ được đi qua các phòng có độ khó \(\le a\), hãy tính xem bạn có thể thu thập được bao nhiêu loại kẹo khác nhau trong vùng bạn đi đến.

Ràng buộc: mức độ bảo vệ của các phòng đôi một khác nhau.

\InputFile

• Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(Q\) (\(1 \le R \times C \le 10000\))
• \(R\) dòng tiếp theo: mỗi dòng gồm \(C\) số nguyên \(A_{i,j}\) (\(1 \le A_{i,j} \le 10^9\))
• \(R\) dòng tiếp theo: mỗi dòng gồm \(C\) số nguyên \(B_{i,j}\) (\(1 \le B_{i,j} \le 10000\))

• \(Q\) dòng tiếp theo, mỗi dòng ghi lần lượt một trong hai truy vấn sau:

• 1 \(x\) \(y\) \(b\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le b \le 10000;\)

• 2 \(x\) \(y\) \(a\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le a \le 10^9;\)

\OutputFile

Với mỗi truy vấn loại 2, in ra một dòng --- số lượng loại phòng khác nhau bạn có thể tiếp cận được.

\Scoring

• Subtask 1 (\(10\%\) số điểm): \(R = 1\), \(1 \le Q \le 1000\), \(A_{1,j} = j\) và không có truy vấn loại 1.
• Subtask 2 (\(20\%\) số điểm): \(1 \le Q \le 100\)
• Subtask 3 (\(24\%\) số điểm): Không có truy vấn loại \(1\).
• Subtask 4 (\(20\%\) số điểm): \(R = 1\), \(1 \le Q \le 10^5\)
• Subtask 5 (\(26\%\) số điểm): Không giới hạn gì thêm

Example

3 3 4
6 2 1
8 7 4
3 9 5
1 2 1
1 2 3
1 3 4
2 2 3 6
1 1 2 1
2 2 3 6
2 2 2 4

4
3
0