Bài tập

Vài hôm trước, A Ton đã võ mồm với bạn thân đến mức hai người ... nghỉ chơi. Vì tò mò, nhóm bạn
trong lớp muốn xem đoạn tin nhắn giữa hai người, nhưng điện thoại cậu lại đặt mật khẩu.
Mật khẩu này gồm đúng n chữ số, được lấy từ dãy số vô hạn:

\begincenter
\(12345678910111213141516171819...\)
\endcenter

Trong đó, chữ số thứ \(i\) trong mật khẩu chính là chữ số ở vị trí \(a_i\) trong dãy số trên.
Hãy giúp nhóm bạn xuất ra dãy mật khẩu của A Ton.

Input

Dữ liệu vào HACMAY.INP:

• Dòng đầu: số nguyên \(n\) \((1 \leq n \leq 10^5)\).
• Dòng thứ hai: \(n\) số nguyên \(a_i\) \((1 \leq a_i \leq 10^{18})\).

Output

Dữ liệu ra HACMAY.OUT:

• In ra \(n\) chữ số tương ứng với các vị trí trong dãy vô hạn.

Example

6
1 23 31 10 33 11

160110

Scoring

Ràng buộc:

• \(20\%\) test: \(n \leq 10^3, a_i \leq 10^3\).
• \(20\%\) test: \(n \leq 10^3, a_i \leq 10^6\).
• \(20\%\) test: \(n \leq 10^3, a_i \leq 10^{12}\).
• \(40\%\) test còn lại: Không có ràng buộc thêm.

Taki có một cây gồm \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Ban đầu, tất cả các cạnh đều được tô màu \(0\).

Anh ấy sẽ thực hiện \(k\) thao tác. Trong thao tác thứ \(i\), Taki chọn hai đỉnh \(x_i\) và \(y_i\), sau đó tô tất cả các cạnh trên đường đi ngắn nhất từ \(x_i\) đến \(y_i\) bằng màu \(i\). Nếu một cạnh đã được tô màu trước đó, màu mới sẽ ghi đè lên màu cũ.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((2 \leq n \leq 5 \times 10^5,\ 1 \leq k \leq 5 \times 10^5)\) --- số đỉnh của cây và số màu.
• Mỗi dòng trong \(n - 1\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i, v_i \leq n)\) --- biểu thị cạnh thứ \(i\) nối hai đỉnh \(u_i\) và \(v_i\). Đảm bảo rằng các cạnh tạo thành một cây.
• Mỗi dòng trong \(k\) dòng tiếp theo chứa hai số nguyên \(x_i\) và \(y_i\) \((1 \leq x_i, y_i \leq n)\) --- mô tả thao tác tô màu đường đi từ đỉnh \(x_i\) đến \(y_i\) bằng màu \(i\).

Output

Gọi \(d(i)\) là màu cuối cùng của cạnh thứ \(i\) theo thứ tự xuất hiện của input.
In ra \(\prod \max(d(i), 1)\) \(mod\) \((10^9+7)\)

Example

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

8

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

48

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 20 & \(n, k \leq 2000\)

2 & 25 & \(u_i = i\), \(v_i = i + 1\) với mọi \(i\)

3 & 20 & \(n, k \leq 10^5\)

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

\hline
\endtabular

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.

Ở bài toán cuối cùng này, bạn được cho một đơn đồ thị vô hướng \(G\) gồm \(n\) đỉnh và \(m\) cạnh. Đồ thị này liên thông, nghĩa là với mọi cặp đỉnh trong đồ thị thì tồn tại ít nhất một đường đi giữa chúng.

Như ta đã biết về khái niệm cầu trong đồ thị. Cầu là một cạnh đặc biệt sao cho nếu xóa cạnh đó đi thì đồ thị mất đi tính liên thông của nó. Bài toán này không phải là đếm cầu bình thường, ta định nghĩa một cầu đặc biệt là một cạnh sao cho khi xóa hai đỉnh đầu mút của cạnh thì \(n-2\) đỉnh còn lại của \(G\) không liên thông.

Nhiệm vụ cuối cùng của bạn là đếm số lượng cầu đặc biệt có trong đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(4 \le n \le 100000\), \(n - 1 \le m \le 300000\)) --- số lượng hòn đảo và số lượng cây cầu.

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(b_i\) (\(1 \le a_i, b_i \le n\)) --- biểu diễn rằng có một cây cầu nối giữa đảo \(a_i\) và đảo \(b_i\).

Đảm bảo rằng đồ thị không có không có hai cạnh kết nối cùng một cặp đỉnh.

Output

In ra một số nguyên duy nhất --- số lượng cây cầu có tính chất đặc biệt như đã mô tả.

Example

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

1

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

4

Scoring

• Subtask 1 (13 điểm): \(n \le 100\), \(m \le 300\)
• Subtask 2 (17 điểm): \(n \le 1000\), \(m \le 3000\)
• Subtask 3 (25 điểm): \(n \le 1000\)
• Subtask 4 (12 điểm): \(m - n \le 20\)
• Subtask 5 (33 điểm): Không có ràng buộc bổ sung