Bài tập

Cho một mảng \(A[1], A[2], \ldots, A[n]\) gồm \(n\) phần tử. Bạn cần thực hiện \(m\) truy vấn để biến đổi mảng theo quy tắc sau.

Mỗi truy vấn có dạng \((L, R, v, p)\), trong đó:

• Tính số lượng các phần tử trong đoạn \(A[L], A[L+1], \ldots, A[R]\) nhỏ hơn \(v\). Gọi kết quả này là \(k\).
• Cập nhật giá trị \(A[p]\) theo công thức:
  \(A[p]\) = \(\left\lfloor \frac{u \cdot k}{R - L + 1} \right\rfloor\)
  trong đó \(\lfloor x \rfloor\) là phép chia nguyên (bỏ phần dư).

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(u\) \((1 \leq n, m \leq 2 \times 10^5\), \(1 \le u \le 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(A[1], A[2], \ldots, A[n]\) \((0 \leq A[i] \leq u)\).
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L, R, v, p\) \((1 \leq L \leq R \leq n, 1 \leq p \leq n, 0 \leq v \leq u)\).

Output

Sau khi thực hiện toàn bộ \(m\) truy vấn, xuất \(n\) số trên một dòng, biểu diễn giá trị cuối cùng của mảng \(A\).

Example

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

2
7
0
9
8
2
8

Scoring

• Có \(20\%\) số điểm ứng với \(n, m \le 10^3\).
• \(80\%\) số điểm còn lại không có ràng buộc thêm.

Một vùng đất hình chữ nhật có thể xem như một lưới ô vuông tạo bởi \(n\) dòng và \(m\) cột. Trên vùng đất đó, người ta đã xây dựng \(h\) đường ngang và \(v\) đường dọc. Các đường này là những đường thẳng đi qua biên của các ô trên cùng dòng hay cùng cột, bắt đầu và kết thúc trên biên của vùng đất. Các đường ngang được đánh số từ \(1\) đến \(n+1\) từ trên xuống dưới và các đường dọc được đánh số từ \(1\) đến \(m+1\) từ trái sang phải.

Để lên kế hoạch xây dựng nhà ở, người ta khảo sát vùng đất để mỗi ngôi nhà có thể xây dựng trên một mảnh đất hình vuông có diện tích \(k \times k\). Tất cả các hình vuông dựng nhà đều có diện tích bằng nhau, không phủ lên nhau, không phủ lên các con đường. Chúng có thể giáp hoặc không giáp với các con đường. Không có ô đất nào để trống. Để tiện tính toán chúng ta bỏ qua độ rộng của các con đường.

Yêu cầu: Hãy tìm những giá trị \(k\) thỏa mãn điều kiện xây dựng nhà cho dự án.

Input

Ghi ra tệp văn bản CAU2.INP:

• Dòng đầu tiên chứa ba số nguyên \(n, m, h, v\) \((1 \leq n, m \leq 10^{18}, 0 \leq h \leq 2 \times 10^5, 0 \leq v \leq 2 \times 10^5)\).

• Nếu \(h > 0\) thì dòng tiếp theo chứa \(h\) số nguyên \(h_{i}, i = 1, 2, ..., h\) \((1 \leq h_{i} \leq n + 1, 1 \leq i \leq h)\) là chỉ số các con đường ngang, tương tự nếu \(v > 0\) thì dòng tiếp theo chứa các \(v_{i}, i = 1, 2, ..., v\) \((1 \leq v_{i} \leq m + 1, 1 \leq i \leq v)\) là chỉ số của các đường dọc. Không có trường hợp \(h = 0\) và \(v > 0\) hay \(h > 0\) và \(v = 0\). Các \(h_{i}\) và \(v_{i}\) có thể trùng nhau.

• Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra tệp văn bản CAU2.OUT:

• Dòng đầu ghi một số là các giá trị \(k\) tìm được;

• Dòng thứ hai là các giá trị \(k\) tìm được, các số ghi cách nhau dấu cách và theo thứ tự tăng dần.

Example

2 4 0 0

2
1 2 

6 8 1 1
3
3

2
1 2 

44 36 3 6
25 33 9
9 37 9 21 29 9

3
1 2 4 

Scoring

• \(50\%\) số điểm có \(h = 0\) và \(v = 0\).

• \(50\%\) số điểm có \(h > 0\) và \(v > 0\). Không có hình chữ nhật nào được tạo ra bởi việc chia của của các con đường này có kích thước cạnh lớn hơn \(10^{14}\).

Một xâu được gọi là đối xứng nếu đọc từ trái qua phải và đọc từ phải qua trái đều giống nhau.

Ví dụ xâu "aba", "abba" là xâu đối xứng; còn xâu "abc", "abca" thì không.

Bạn được cho \(N\) xâu, như vậy sẽ có \(N \times N\) cặp xâu. Bạn hãy đếm xem trong \(N \times N\) cặp xâu này, có bao nhiêu cặp mà khi nối xâu thứ hai vào sau xâu thứ nhất sẽ cho ra một xâu đối xứng.

Input

• Dòng đầu ghi một số \(N\).

• \(N\) dòng sau mỗi dòng mô tả một xâu, bắt đầu là độ dài của xâu, sau đó là một dấu cách và tiếp theo là nội dung của xâu. (Xâu chỉ gồm các chữ cái latin thường và có độ dài nguyên dương)

Dữ liệu vào luôn đảm bảo tổng độ dài các xâu không quá 1000000

Output

• Ghi ra một số duy nhất là số cặp xâu tìm được.

Example

3
1 a
2 ab
2 ba

5

An và Bình đang chơi một trò chơi trốn tìm trong ngôi nhà của họ. Ngôi nhà có \(n\) phòng
và \(m\) cặp phòng được nối với nhau bằng cửa. Các phòng được đánh số từ \(1\) đến \(n\),
và giữa bất kỳ hai phòng nào cũng tồn tại một đường đi.

Bình có một chiến thuật trốn như sau: mỗi khi An bước vào phòng \(v\), Bình sẽ trốn trong phòng \(a_v\).
Ở thời điểm bắt đầu, An chọn phòng xuất phát \(v_0\), và Bình sẽ trốn trong phòng \(a_{v_0}\).

Mỗi lượt chơi diễn ra theo thứ tự:
(1) An chọn một phòng kề với phòng hiện tại của mình và di chuyển sang đó.
(2) Ngay lập tức, Bình biết An đang ở đâu và lập tức di chuyển (có thể đi qua nhiều phòng trong một lượt) tới phòng \(a_u\) tương ứng với phòng mới của An.

Trò chơi kết thúc ngay khi cả hai ở trong cùng một phòng.

Với mỗi phòng xuất phát của An, hãy xác định xem An có thể tìm được Bình trong số bước hữu hạn hay không.
Nếu có, hãy tính số bước ít nhất An cần để chắc chắn tìm thấy Bình, giả sử cả hai đều chơi tối ưu:
An muốn kết thúc trò chơi càng sớm càng tốt, còn Bình muốn kéo dài thời gian càng lâu càng tốt.

\InputFile

Dòng đầu gồm hai số nguyên \(n, m\)
(\(1 \le n \le 2 \cdot 10^5\), \(n - 1 \le m \le \min(5 \cdot 10^5, \frac{n(n-1)}{2})\)) ---
số phòng và số cặp phòng có cửa nối.

Dòng thứ hai gồm \(n\) số nguyên \(a_i\) (\(1 \le a_i \le n\)), mô tả chiến thuật trốn của Bình.

Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số \(x_i, y_i\) (\(1 \le x_i, y_i \le n\), \(x_i \ne y_i\)),
cho biết phòng \(x_i\) và phòng \(y_i\) có cửa nối trực tiếp. Giữa hai phòng bất kỳ có nhiều nhất một cửa.

\OutputFile

In ra \(n\) số.
Số thứ \(i\) là số bước ít nhất để An có thể tìm thấy Bình nếu bắt đầu từ phòng \(i\),
hoặc \(-1\) nếu An không thể tìm thấy Bình.

\Scoring

\begincenter
\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 15 &
\(\, n \le 1000,\; m \le 2000\)

2 & 25 &
\(m = n - 1\)

3 & 30 &
Bình sẽ không bao giờ trốn trong phòng liền kề hoặc trùng với phòng An đang đứng,
và cấu trúc ngôi nhà đảm bảo trò chơi kết thúc trong không quá \(5\) phòng khác nhau

4 & 30 &
Không có ràng buộc bổ sung.

\hline
\endtabular
\endcenter

\Examples

\beginexample
\exmp
4 4
3 4 1 2
1 2
2 3
3 4
4 1

-1 -1 -1 -1

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

1 2 2 2 1 1 1 1

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

0 1 1 2 1 1 2 1 1

\endexample

\Note

Trong ví dụ thứ hai:
An di chuyển từ phòng \(4\) sang phòng \(8\) ở lượt đầu tiên, và ở lượt thứ hai quay trở lại phòng \(4\).
Bình buộc phải đi qua phòng \(4\) để có thể đi từ phòng \(7\) về phòng \(1\),
vì vậy An tìm được Bình sau \(2\) bước.

\endproblem