Bài tập

Trong một dải ngân hà xa xôi, có hai chuỗi các hành tinh được đánh số. Chuỗi hành tinh đầu tiên gồm \(n\) hành tinh có giá trị năng lượng \(a_1, a_2, \ldots, a_n\). Chuỗi hành tinh thứ hai gồm \(m\) hành tinh có giá trị năng lượng \(b_1, b_2, \ldots, b_m\).

Một hành tinh được coi là "đẹp" nếu nó có thể được kết nối bằng một cây cầu ánh sáng với một hành tinh khác. Cụ thể, một hành tinh có giá trị năng lượng \(x\) được gọi là "đẹp" nếu tồn tại hai hành tinh \(i, j\) thuộc chuỗi thứ hai (\(1 \le i \le j \le m\)) sao cho giá trị năng lượng của chúng khi kết hợp bằng phép toán bitwise OR (\(b_i | b_{i+1} | \ldots | b_j\)) bằng với \(x\).

Nhà thám hiểm vũ trụ Alex đang thực hiện một nhiệm vụ đặc biệt. Anh ấy có \(Q\) câu hỏi, mỗi câu hỏi yêu cầu đếm số cặp hành tinh \((i, j)\) trong chuỗi thứ nhất (\(L \le i \le j \le H\)) sao cho giá trị phép toán bitwise AND (\(a_i \& a_{i+1} \& \ldots \& a_j\)) bằng với giá trị năng lượng của một hành tinh "đẹp" bất kỳ.

Yêu cầu: Với mỗi câu hỏi, hãy giúp Alex tìm câu trả lời.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, m, Q\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\).
• Dòng thứ ba chứa \(m\) số nguyên không âm \(b_1, b_2, \ldots, b_m\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, H\) mô tả một truy vấn.

Output

• Ghi ra \(Q\) dòng, mỗi dòng là kết quả cho một truy vấn tương ứng.

Example

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

3
3
5

Scoring

• Trong tất cả các test: \(n, m, Q, a_i, b_i \le 2 \cdot 10^5\).
• Subtask 1 (16% số điểm): \(n \le 1000\) và \(a_i \le 1000\) và \(m \le 10\).
• Subtask 2 (20% số điểm): \(Q = 1\) và \(m \le 100\).
• Subtask 3 (24% số điểm): \(Q = 1\).
• Subtask 4 (40% số điểm): Ràng buộc chuẩn.

Alice xây dựng một đồ thị có dạng là cây gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\), trong đó đỉnh \(1\) làm gốc. Đỉnh \(i\ (i > 1)\) sẽ có cạnh nối tới cha của nó là đỉnh \(p_i\ (1 \le p_i < i)\) với khoảng cách là \(w_i\). Số đỉnh nằm trên đường đi đơn từ nút gốc \(1\) đến một nút lá bất kỳ không vượt quá \(21\). Bob đề xuất một trò chơi trên cây như sau: Với hai số nguyên dương \(s\) và \(d\), Bob sẽ chọn \(s\) nút có số hiệu không vượt quá \(d\) để đặt \(s\) quả táo, Alice sẽ xuất phát tại đỉnh gốc \(1\) và tìm cách đi với tổng độ dài đường đi là ngắn nhất để thu thập được hết \(s\) quả táo rồi quay về đỉnh gốc.

Bob muốn làm khó Alice nên tìm cách đặt \(s\) quả táo để tổng độ dài đường đi của Alice là lớn nhất.

Yêu cầu: Cho cây mà Alice tạo và \(q\) lần chơi, mỗi lần chơi mô tả bằng hai số nguyên \(s\) và \(d\). Với mỗi lần chơi hãy đưa ra tổng độ dài đường đi của Alice trong trường hợp Bob biết cách đặt tối ưu.

Input

• Dòng đầu là hai số nguyên dương \(n, q\ (n \le 10^5)\).
• Dòng thứ hai chứa \(n - 1\) số nguyên dương \(p_2, p_3, \ldots, p_n\).
• Dòng thứ ba chứa \(n - 1\) số nguyên dương \(w_2, w_3, \ldots, w_n\ (w_i \le 10^9\) với \(2 \le i \le n)\).
• \(q\) dòng sau, mỗi dòng chứa hai số nguyên dương \(s, d\ (s, d \le n)\) mô tả một lần chơi.

Output

• Gồm \(q\) dòng, mỗi dòng là tổng độ dài đường đi của Alice trong trường hợp Bob biết cách đặt tối ưu cho lần chơi tương ứng.

Example

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

6
12
20
24

Scoring

• Có \(30\%\) số lượng test của bài có \(q = 1\) và \(n \le 100\).
• Có \(20\%\) số lượng test của bài có \(q = 1\).
• Có \(30\%\) số lượng test khác của bài có \(p_i = 1\) với \(2 \le i \le n\).
• Có \(20\%\) số lượng test còn lại không có ràng buộc nào thêm.

Bạn có một mảng \(a\) , gồm \(n\) số nguyên \(a_{1} , a_{2} , ..., a_{n}\) . Bạn được phép thực hiện hai thao tác trên mảng này:

• Tính tổng các phần tử mảng hiện tại trên đoạn \([l,r]\) , nghĩa là tính \(a_{l} + a_{l + 1} + ... + a_{r}\).

• Áp dụng phép toán xor với một số \(x\) cho trước cho mỗi phần tử của mảng trên đoạn \([l,r]\) , nghĩa là \(a_{i}:=a_{i}\) \(xor\) \(x\) với \(l \leq i \leq r\). Thao tác này thay đổi chính xác \(r - l + 1\) phần tử của mảng.

Bạn có một danh sách gồm \(m\) thao tác thuộc một trong hai loại trên. Nhiệm vụ của bạn là thực hiện tất cả các thao tác đã cho, đối với mỗi thao tác tính tổng, in ra kết quả của thao tác đó.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) \((1 ≤ n ≤ 2.10^5)\) - kích thước của mảng.

Dòng thứ hai chứa các số nguyên không âm \(a_{1} , a_{2} , ..., a_{n}\) \((0 ≤ a_{i} ≤ 10^6)\) - mảng ban đầu.

Dòng thứ ba chứa số nguyên \(m\) \(( 1 ≤ m ≤ 2.10^5 )\) - số truy vấn.
Dòng thứ \(i\) trong số \(m\) dòng tiếp theo đầu tiên chứa số nguyên \(t_i\) \((1 ≤ t_{i} ≤ 2)\) - loại thao tác thứ i .

Nếu \(t_{i} = 1\) thì đây là thao tác tính tổng, nếu \(t_{i} = 2\) thì đây là thao tác thay đổi các phần tử mảng. Nếu thao tác thứ \(i\) thuộc loại \(1\) , thì tiếp theo là hai số nguyên \(l_{i} , r_{i}\) \(( 1 ≤ l_{i} ≤ r_{i} ≤ n )\). Nếu phép toán thứ \(i\) thuộc loại \(2\) , thì tiếp theo là ba số nguyên \(l_{i} , r_{i} , x_{i}\) \((1 ≤ l_{i} ≤ r_{i} ≤ n , 1 ≤ x_{i} ≤ 10 ^ 6 )\). Các số trên các dòng được phân tách bằng dấu cách.

Output

Với mỗi thao tác loại \(1\), in ra trên một dòng là kết quả của thao tác.

Example

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

26
22
0
34
11

Scoring

\(50\%\) số test tương ứng \(50\%\) số điểm có \(n, m <= 10^3\).

\(50\%\) số test tương ứng \(50\%\) số điểm còn lại không có ràng buộc gì thêm.

Thành phố Hồ Chí Minh (thường được gọi là Sài Gòn) là một thành phố ở miền nam Việt Nam nổi tiếng với vai trò nòng cốt trong chiến tranh Việt Nam. Sài Gòn cũng được biết đến với địa danh của thực dân Pháp, trong đó có Nhà thờ Đức Bà được xây dựng hoàn toàn bằng nguyên liệu nhập khẩu từ Pháp và Bưu điện trung tâm được xây dựng vào thế kỷ 19. Quán ăn nằm dọc các đường phố Sài Gòn, nhất là xung quanh chợ Bến Thành nhộn nhịp.

Đến thành phố Hồ Chí Minh, các bạn có thể tham quan những địa điểm sau:

• Trụ sở Ủy ban Nhân dân Thành phố

• Bến Nhà Rồng: nơi Chủ tịch Hồ Chí Minh ra đi tìm đường cứu nước, Bến Nhà Rồng còn có tên gọi khác là bảo tàng Hồ Chí Minh tại thành phố Hồ Chí Minh, ở trong có các kỉ vật của Bác Hồ.

• Nhà hát lớn
• Bưu điện Trung tâm

• Dinh Độc lập: Công trình được thiết kế theo phong thuỷ và kiến trúc phương Đông nhưng lại rất hiện đại. Tham quan dinh Độc Lập, du khách có thể chiêm ngưỡng tận mắt nhiều vật phẩm từ chế độ cũ cũng như những chứng tích ghi dấu thời khắc ngày độc lập 30 tháng 4, 1975. Giờ mở cửa: Sáng 7h30 -- 11h00, chiều từ 13h00 -- 16h00 (hàng ngày); Địa chỉ: 135 Nam Kỳ Khởi Nghĩa, P.Bến Nghé, Q.1; Giá vé: Người lớn:30.000VND/người/lần, sinh viên: 15.000VND/người/lần, học sinh: 3.000VND/người/lần, khách theo đoàn từ 20 người sẽ được giảm 1/3 giá vé; Gửi xe máy tại: Cổng Dinh Độc Lập bên đường Nguyễn Du, bãi gửi xe ở công viên Tao Đàn trên đường Huyền Trân Công Chúa.

• Nhà thờ Đức Bà: Đây là khu vực trung tâm thuộc Q.1, Thành phố Hồ Chí Minh. Khu vực Nhà Thờ thể hiện rõ rệt "tính cách" của thành phố Sài Gòn. Gần nhà thờ cổ kính là hình ảnh đối lập với những tòa cao ốc bê tông cốt thép thời hiện đại. Từ nhà thờ Đức Bà, bạn có thể sang thăm dinh Độc Lập, mua sắm ở Diamond Plaza, dạo phố Đồng Khởi, qua Hồ Con Rùa, uống cà phê bệt ở đường Hàn Thuyên. Tọa lạc ngay trục đường chính ở trung tâm thành phố, hiện nay nhà thờ Đức Bà dần trở thành biểu tượng của thành phố Sài Gòn. Nơi đây nổi bật với kiến trúc Châu Âu kết hợp phong cách Roman và Gothic tuyệt đẹp, cùng cặp chuông lớn nhất Việt Nam. Nhà thờ Đức Bà là ngôi thánh đường đẹp nhất và quan trọng nhất của giáo phận Sài Gòn, niềm tự hào của người dân thành phố. Khu vực xung quanh nhà thờ Đức Bà có cảnh quan đẹp nhất tại Sài Gòn.

• Thảo Cầm viên
• Công viên 23/9
• Bảo tàng Chứng tích chiến tranh: Du khách đến đây sẽ cảm nhận chân thực nhất về một thời kỳ chiến tranh ác liệt, để thêm trân trọng những gì đang có ở hiện tại. Các hiện vật như máy bay, đại bác, xe tăng, máy chém và hai ngăn "chuồng cọp" được xây dựng đúng kích thước ở nhà tù Côn Đảo. Ngoài ra còn có phòng trưng bày về Chiến tranh biên giới Tây Nam, chiến tranh bảo vệ biên giới phía Bắc, vấn đề quần đảo Trường Sa, âm mưu của các thế lực thù địch… Giờ mở cửa: Sáng 7h30 -- 12h00, 13h30 -- 17h00 (hàng ngày); Vé vào cổng: 15.000VND/lượt/người (khách nước ngoài), 2.000VND/lượt (khách Việt Nam); Địa chỉ: Số 28 đường Võ Văn Tần, Q.3.
• Bảo tàng Chiến dịch Hồ Chí Minh

Quân hiện tại đang sinh sống và học tập tại thành phố Hồ Chí Minh. Hiện tại, thành phố Hồ Chí Minh có 16 quận : Quận 1, quận 3, quận 4, quận 5, quận 6, quận 7, quận 8, quận 10, quận 11, quận 12, quận Tân Bình, quận Tân Phú, quận Bình Tân, quận Bình Thạnh, quận Gò Vấp và quận Phú Nhuận. Tuy nhiên, trong một tương lai nào đó, thành phố Hồ Chí Minh lúc này có \(n\) quận, được kết nối với nhau bằng \(n - 1\) con đường nối trực tiếp giữa hai quận khác nhau, đảm bảo giữa \(n\) quận đều có thể đi đến được với nhau bằng những con đường này. Tuy nhiên, vì một trận mưa lớn, tất cả các con đường đều bị ngập và các quận đều bị cô lập.

Tình hình này không thể diễn ra liên tục, vì nó ảnh hưởng rất lớn tới thành phố. Chính phủ quyết định sẽ dùng máy hút nước siêu khổng lồ để hút nước tại các con đường. Máy hút nước này được sử dụng như sau:

• Có \(m\) kế hoạch hút nước. Kế hoạch hút nước thứ \(i\) sẽ hút nước trên một số con đường, sao cho sau khi hút nước xong, các quận \(a_{1}, a_{2}, ..., a_{s}\) sẽ đi đến được với nhau, và số con đường hút nước phải ít nhất. Lưu ý: dù các con đường ở các kế hoạch trước đã hút nước, ở kế hoạch hiện tại vẫn phải hút.

Yêu cầu: Đếm số con đường bị ảnh hưởng bởi ít nhất \(k\) kế hoạch.

Input

Dòng đầu tiên là ba số nguyên dương \(n, m, k\).

\(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(a_{i}\) và \(b_{i}\) - con đường kết nối hai quận \(a_{i}\) và \(b_{i}\) \((1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i}\).

\(m\) dòng tiếp theo, mỗi dòng gồm :

• số nguyên dương \(s\) là số quận đi đến được với nhau sau khi hút nước.

• tiếp theo là \(s\) số nguyên dương \(a_{1}, a_{2}, ..., a_{s}\) $(1 \leq a_{i} \leq n, a_{i} \neq a_{j} (i \neq j)) $.

Dữ liệu đảm bảo rằng tổng của các \(s\) trong các kế hoạch không vượt quá \(S\).

Output

Dòng đầu tiên là số nguyên không âm \(r\), số con đường bị ảnh hưởng bởi ít nhất \(k\) kế hoạch.

Dòng thứ hai là chỉ số của các con đường bị ảnh hưởng, theo thứ tự tăng dần.

Example

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

2
2 3 

Scoring

Trong tất cả các testcase, \(2 \leq s_{i} \leq n, S \leq 100000, 1 \leq k \leq m \leq 50000\).

Có \(8\%\) số test tương ứng với \(8\%\) số điểm có \(n \leq 10000, S \leq 2000\).

Có \(15\%\) số test tương ứng với \(15\%\) số điểm có \(n \leq 10000, m \leq 2000\).

Có \(7\%\) số test tương ứng với \(7\%\) số điểm có mỗi quận chỉ kết nối tối đa \(2\) quận khác.

Có \(29\%\) số test tương ứng với \(29\%\) số điểm có \(k = m, s_{i} = 2\).

Có \(16\%\) số test tương ứng với \(16\%\) số điểm có \(k = m\).

Có \(25\%\) số test tương với với \(25\%\) số điểm còn lại không có ràng buộc gì thêm.