Ngày xửa ngày xưa, Gấu Trắng là một thần dân trong Thế Giới Âm Nhạc – vương quốc được điều phối bởi sức mạnh của những thanh tấu, giai điệu. Nơi đây, tồn tại một thực thể tối thượng mang tên Quả Cầu Âm Thanh. Nó là thứ báu vật vô song, chỉ được chinh phục, sở hữu bởi một cá nhân xuất chúng mỗi hàng trăm thế hệ, và là biểu tượng tối cao của sự xứng đáng, được công nhận bởi thần dân của cả quá khứ, hiện tại, tương lai trong Vương Quốc Âm Nhạc. Và nó đã trong trạng thái vô chủ trong suốt hàng nghìn năm nay!

Để sở hữu Quả Cầu Âm Thanh, một thần dân cần phải có khả năng vượt ải diệt boss, chiến đấu với quái vật, thể hiện và chứng minh tài năng của bản thân với tất cả công dân trong vương quốc, và cuối cùng, tấu được khúc Giai Điệu Ngàn Năm – khúc nhạc huyền thoại, là chìa khóa cuối cùng trong hành trình chinh phục Quả Cầu Âm Thanh. Nghe nói… trong chính cái tên của giai điệu này, ẩn chứa một sức mạnh nghịch đảo khủng khiếp…

Với khát vọng chinh phục Quả Cầu Âm Thanh, Gấu Trắng quyết định chuẩn bị hành trang cho chuyến phiêu du của mình. Để nghiên cứu về Giai Điệu Ngàn Năm, cậu nhận ra mình cần rất nhiều kỹ năng và tư duy giải quyết vấn đề. Gấu Trắng quyết định bắt đầu luyện tập bằng bài toán sau:

Gấu được cho một dãy số ~a~ gồm ~N~ phần tử, phần tử thứ ~i~ có giá trị là ~a_i~. Gấu sẽ phải lựa ra một dãy con của dãy ~a~. Một dãy con ~k~ phần tử của dãy ~a~ được định nghĩa là dãy ~a_{i_1}, a_{i_2}, \ldots, a_{i_k}~ ~(1 \le i_1 < i_2 < ... < i_k \le N)~. Tổng của dãy con ~k~ phần tử mà Gấu chọn sẽ là ~a_{i_1} + a_{i_2} + \ldots + a_{i_k}~ . Tìm dãy con có số lượng phần tử là lẻ, sao cho tổng của dãy con này là lớn nhất.

Input

• Dòng đầu chứa số ~N~ ~(1 \le N\le 10^6)~.

• Dòng tiếp theo chứa ~N~ số nguyên ~a_1,a_2,\ldots,a_N~ ~(|a_i| \leq 10^9)~.

Output

Một số duy nhất là đáp án của bài toán: tổng lớn nhất của một dãy con có lẻ phần tử.

Scoring

• Subtask ~1~ (~18\%~): ~n \leq 20~.

• Subtask ~2~ (~14\%~): ~\min(a_1,a_2,\ldots,a_n) = \max(a_1,a_2,\ldots,a_n)~.

• Subtask ~3~ (~23\%~): ~a_i \geq 0~ ~(1 \leq i \leq n)~.

• Subtask ~4~ (~21\%~): ~a_1 \geq a_2 \geq \ldots \geq a_n~.

• Subtask ~5~ (~24\%~): Không có giới hạn gì thêm.

Sample Input 1

6
-1 2 -3 -1 -2 4

Sample Output 1

5

Notes

Chọn ~3~ phần tử ~a_2, a_4, a_6~ có giá trị ~2 + (-1) + 4 = 5~.

Gấu Trắng phát hiện bản thân quên mất một điều: ngoài kỹ năng giải mã, cậu còn cần phải đánh bại quái vật bằng tiếng đàn, chứng minh tài năng âm nhạc trong thế giới này mới xứng đáng sở hữu Quả Cầu Âm Thanh. Với mong muốn level up sức mạnh âm nhạc, cậu đã cùng hàng nghìn thí sinh khác tham dự Kỳ Tranh Tài để dành lấy Bí Kíp Âm Nhạc – quyển cẩm nang sẽ giúp cậu tiến xa trên con đường của chính mình.

Kỳ Tranh Tài đã chính thức bắt đầu! Câu hỏi có nội dung như sau:

Cho một mảng ~a~ gồm ~N~ phần tử nguyên. Hãy chọn ra một số đoạn con không đụng nhau từ mảng ~a~ (đoạn con thứ ~i~ và đoạn con thứ ~i+1~ được ngăn cách bởi ít nhất một vị trí trong mảng ~a~) sao cho tổng của các phần tử đầu và cuối của tất cả các đoạn con được chọn chia hết cho ~3~, đồng thời tổng giá trị các phần tử trong các đoạn đó là lớn nhất.

Nói cách khác, hãy chọn ~k~ (~k~ bất kỳ) đoạn con thỏa các điều kiện sau:

• Một cách chọn hợp lệ là chọn ~k~ đoạn con ~[u_1, v_1], [u_2, v_2], ..., [u_k, v_k]~ thỏa đồng thời tất các điều kiện sau:

  • ~1 \le u_1 \le v_k \le N~.

  • ~u_i \leq v_i~ (~1 \leq i \leq k~).

  • ~v_i + 1 < u_{i+1}~ (~1 \leq i < k~).

  • ~\sum_{i=1}^k a_{u_i} + a_{v_i}~ ~\vdots~ ~3~.

• Gọi ~s_i~ là tổng của đoạn con thứ ~i~ (~s_i = \sum_{j=u_i}^{v_i} a_j~). Tìm cách chọn ~k~ đoạn sao cho tổng ~S~ lớn nhất (với ~S = \sum_{i=1}^{k} s_i~, tức ~S~ là tổng của tất cả ~k~ đoạn).

• Không chọn bất kì một đoạn con nào cũng là một cách chọn hợp lệ.

Input

• Dòng đầu chứa số ~N~ ~(1 \le N\le 10^6)~.

• Dòng tiếp theo chứa ~N~ phần tử biểu diễn mảng ~a~ (~|a_i| \le 10^9~).

Output

Một số duy nhất là tổng ~S~ lớn nhất có thể của bài toán.

Scoring

• Subtask ~1~ (~15\%~): ~n \leq 20~.

• Subtask ~2~ (~15\%~): Mọi phần tử trong mảng đều chia hết cho ~3~.

• Subtask ~3~ (~20\%~): ~n \leq 100~.

• Subtask ~4~ (~30\%~): ~n \leq 1000~.

• Subtask ~5~ (~20\%~): Không có giới hạn gì thêm.

Sample Input 1

9
-1 2 -3 -5 -3 1 -2 -2 4

Sample Output 1

6

Notes

• Cách chọn: 2 đoạn ~[2, 2], [9, 9]~.

• Tổng lớn nhất tìm được là ~6 = a_2 + a_9 = 2 + 4~.

• Điều kiện 2 được thỏa mãn: ~a_2 + a_2 + a_9 + a_9 = 2 + 2 + 4 + 4 = 12~ ~\vdots~ ~3~

Sau khi chiến thắng Kỳ Tranh Tài và giành lấy được Bí Kíp Âm Nhạc, Gấu Trắng tìm hiểu được: một bản nhạc, biểu diễn cho một giai điệu, là một bảng dọc có kích thước ~6 \times 4~ gồm ~24~ số nguyên dương mang ý nghĩa là cao độ của các nốt nhạc.

Với đó, Gấu Trắng tiếp tục hành trình chinh phục Giai Điệu Ngàn Năm của mình. Chướng ngại vật đầu tiên của cậu chính là một con quái vật hung tợn trong rừng cây. Để đánh bại nó, cậu cần hợp nhất hai cành cây trong cánh rừng, tạo thành một chiếc đàn để đối phó với quái vật. Tuy nhiên, Gấu Trắng không biết cách tính điểm sức mạnh của việc hợp nhất hai cành cây này. Bạn hãy hỗ trợ Gấu Trắng giải bài toán sau nhé:

Cho 2 cây là ~A~ và ~B~ với mỗi cây có lần lượt là ~n~ và ~m~ đỉnh. Để tính sức mạnh của việc ghép hai cây, với mọi cặp đỉnh ~(i, j)~ (~i~ là một đỉnh trong ~A~, ~j~ là một đỉnh trong ~B~), ta nối hai đỉnh này lại. Việc nối này sẽ tạo ra một cây mới là ~T~, chi phí của cách ghép này chính là đường kính của cây ~T~ - được định nghĩa là khoảng cách xa nhất giữa hai đỉnh trong cây ~T~, khoảng cách được tính bằng số lượng cạnh nằm trên đường đi đơn giữa hai đỉnh đó.

Sức mạnh của hai cây ~A~ và ~B~ chính là tổng chi phí của mọi cách ghép hai cây đó. Nói cách khác, gọi ~f(x, y)~ là chi phí của việc nối đỉnh ~x~ của cây ~A~ với đỉnh ~y~ của cây ~B~ để tạo thành cây ~T~, hãy tính: $$\sum_{i=1}^{n} \sum_{j=1}^{m} f(i, j)$$

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ (~1 \leq n, n \leq 10^5~), lần lượt là số đỉnh của hai cây.

• Dòng thứ ~i~ trong ~n - 1~ dòng tiếp theo gồm hai số nguyên dương ~x, y~ (~1 \leq x, y \leq n~), miêu tả một cạnh của cây ~A~.

• Dòng thứ ~i~ trong ~m - 1~ dòng tiếp theo gồm hai số nguyên dương ~x, y~ (~1 \leq x, y \leq m~), miêu tả một cạnh của cây ~B~.

Output

Gồm một số nguyên dương duy nhất là đáp án của bài toán trên.

Scoring

• Subtask ~1~ (~20\%~): ~n, m \leq 10^2~.

• Subtask ~2~ (~40\%~): ~n, m \leq 10^3~.

• Subtask ~3~ (~40\%~): ~n, m \leq 10^5~.

Sample Input 1

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

Sample Output 1

53

Notes

- Trên hình là 1 trong 12 cách ghép của test ví dụ 1, nối đỉnh ~1~ của ~A~ và đỉnh ~1~ của ~B~. Khoảng cách xa nhất giữa 2 đỉnh trong cách ghép này là ~3~, vậy nên đường kính là ~3~.

Trước khi tham gia buổi Đại Hòa Nhạc, Gấu Trắng cần tìm cho mình một bản nhạc hoàn hảo nhất để trình diễn. Nhưng sau khi tham khảo rất nhiều nơi, Gấu Trắng nhận ra rằng bản nhạc hoàn hảo nhất phải được chính mình sáng tác nên. Vậy nên cậu đã bắt tay vào sáng tác ra bản nhạc của đời mình!

Biết được từ bài ~3~ rằng khuông nhạc trong Thế Giới Âm Nhạc là một bảng hai chiều, Gấu Trắng quyết định nghiên cứu về cấu trúc này.

Gấu Trắng định nghĩa "độ hoàn hảo" của một bảng hai chiều là tổng bitwise AND~^\dagger~ lớn nhất trong một bảng con của bảng ban đầu, sao cho bảng con này có số lượng phần tử (hay diện tích) nằm trong khoảng cho trước.

Gấu Trắng luyện tập bằng một bài tập như sau: Cho một bảng hai chiều có kích thước ~n \times m~ và hai số nguyên ~L, R~. Hãy tính độ hoàn hảo của bảng này.

Nói cách khác, Gấu Trắng sẽ tìm hình chữ nhật con có diện tích trong khoảng ~[L, R]~ sao cho tổng bitwise AND của các phần tử thuộc hình chữ nhật con đó là lớn nhất.

~^\dagger~ Phép bitwise AND của hai số nguyên, ký hiệu là ~a \mathbin{\&} b~, cho ra một số nguyên ~c~ sao cho trong biểu diễn nhị phân, mỗi bit (chữ số) của ~c~ là tích của hai chữ số tương ứng của ~a~ và ~b~. Ví dụ, ~206 \mathbin{\&} 101 = 68~ vì trong biểu diễn nhị phân, ta có:

• ~1100 1110_2 = 206~ (giá trị ~206~ biểu diễn trong hệ nhị phân là dãy bit ~1100 1110~).
• ~0110 0101_2 = 101~.
• ~0100 0100_2 = 68~.
• ~1100 1110_2 \mathbin{\&} 0110 0101_2 = 0100 0100_2~.

~^\dagger~Tổng bitwise AND của một dãy số ~a_1, a_2, a_3, \cdots, a_p~ là ~a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} \cdots \mathbin{\&} a_p~.

Input

• Dòng đầu chứa bốn số nguyên ~n, m, L, R~ (~1 \leq n, m \leq 1000~, ~1 \leq L \leq R \leq n \times m~).

• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, \cdots, a_{i, m}~ (~0 \leq a_{i, j} \leq 10^9~).

Output

In ra độ hoàn hảo của bảng.

Scoring

• Subtask ~1~ (~15\%~): ~1 \leq n, m \leq 50~.

• Subtask ~2~ (~15\%~): ~1 \leq n, m \leq 300~.

• Subtask ~3~ (~20\%~): ~1 \leq n, m \leq 1000~ và ~R = n \times m~.

• Subtask ~4~ (~20\%~): ~1 \leq n, m \leq 1000~ và ~0 \leq a_{i, j} \leq 1~.

• Subtask ~5~ (~30\%~): Không có giới hạn gì thêm.

Sample Input 1

6 4 4 10
7 11 27 31
8 15 3 19
15 20 5 2
16 22 15 6
29 13 21 1
10 20 25 30

Sample Output 1

4

Notes

Ví dụ, với bảng nhạc mà Gấu Trắng tự sáng tác như trên, độ hoàn hảo chính là bitwise AND của hình chữ nhật con có góc trên trái là ô ~(3, 2)~ và góc dưới phải là ô ~(5, 3)~.

Diện tích của hình chữ nhật này là ~6~ nằm trong khoảng ~[4, 10]~ và bitwise AND là ~20 \space \& \space 5 \space \& \space 22 \space \& \space 15 \space \& \space 13 \space \& \space 21 = 4~.

Lưu ý: ô ở dòng thứ ~i~, cột thứ ~j~ có tọa độ là ~(i, j)~ và có giá trị là ~a_{i, j}~.

Sau bao thời gian chuẩn bị, cuối cùng đã tới ngày Gấu Trắng trình diễn tại buổi Đại Hòa Nhạc. Tuy nhiên, trong lúc duyệt qua bài nhạc của mình, cậu nhận ra bài nhạc còn thiếu một yếu tố vô cùng quan trọng: sự bay bổng. Vậy nên, Gấu Trắng quyết định tăng một tone cho bản nhạc của mình và sẵn sàng biểu diễn!

Chỗ ngồi khán giả có dạng cây, với vị trí sân khấu nằm về phía gốc của cây (sân khấu không phải là gốc). Gốc của cây là đỉnh ~1~. Mỗi đỉnh của cây là một chỗ ngồi. Ban đầu mỗi chỗ ngồi sẽ có giới hạn âm lượng là ~c~: nếu âm lượng tại một chỗ ngồi vượt quá ~c~, giá trị đó sẽ được gán lại thành ~c~.

Gấu Trắng nhận được rất nhiều sự ủng hộ từ khán giả, cậu muốn theo dõi âm thanh vỗ tay từ dưới khán đài. Sẽ có ~q~ sự kiện lần lượt diễn ra như sau:

• clap ~u~ : Một khán giả vỗ tay tại ~u~; lần vỗ tay này không tạo ra âm thanh và không thay đổi âm lượng, nhưng tạo ra sóng âm tại ~u~.

• travel ~d~:

  • Tất cả các sóng âm sẽ lan truyền trong không khí: di chuyển ~d~ chỗ ngồi về phía sân khấu.

  • Khi đi vào một vị trí, sóng âm sẽ tăng âm lượng tại vị trí đó lên ~1~ đơn vị (nhưng không vượt quá giới hạn âm lượng tại vị trí đó). Lưu ý: với mỗi đợt travel, sóng âm không thay đổi âm lượng tại vị trí mà nó bắt đầu di chuyển, chỉ ảnh hưởng đến âm lượng tại các vị trí mà nó đi vào.

  • Mỗi sóng âm sau khi di chuyển đủ ~d~ bước sẽ dừng lại, nhưng không biến mất.

  • Mỗi sóng âm, ngay sau khi đi vào gốc của cây và tăng âm lượng tại gốc, sẽ biến mất, kể cả khi chưa di chuyển đủ số bước theo yêu cầu của đợt travel.

• count ~u~: Tính toán tổng âm lượng của tất cả chỗ ngồi trong cây con gốc ~u~ ở thời điểm hiện tại.

Input

• Dòng đầu tiên chứa ba số nguyên ~n, c, q~ ー số lượng đỉnh trong cây, giới hạn âm lượng ở mỗi đỉnh, và số lượng sự kiện (~1 \leq n, c, q \leq 10^5~).

• Dòng thứ ~i~ trong ~n-1~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ ー có cạnh nối giữa hai đỉnh ~x_i~ và ~y_i~ (~1 \leq x_i, y_i \leq n~, với ~1 \leq i \leq n-1~). Dữ liệu đảm bảo đồ thị là đồ thị cây.

• Mỗi dòng trong ~q~ dòng tiếp theo chứa các sự kiện theo mô tả đề bài, mỗi sự kiện thuộc một trong ba dạng:

  • clap ~u~ (~1 \leq u \leq n~).
  • count ~u~ (~1 \leq u \leq n~).
  • travel ~d~ (~1 \leq d \leq n~).

Output

Với mỗi sự kiện loại count ~u~, in ra tổng âm lượng của tất cả chỗ ngồi trong cây con gốc ~u~ tại thời điểm sự kiện.

Scoring

• Subtask ~1~ (~5\%~): ~1 \leq n, c, q \leq 5000~.

• Subtask ~2~ (~15\%~): ~c = 1~.

• Subtask ~3~ (~40\%~): ~c = 10^5~.

• Subtask ~4~ (~40\%~): Không có giới hạn gì thêm.

Sample Input 1

6 2 10
1 2
2 3
1 4
4 5
4 6
count 1
clap 5
travel 1
count 1
clap 4
clap 3
travel 2
count 1
count 4
count 3

Sample Output 1

0
1
4
1
0

Notes

• Khán đài ban đầu nhìn như sau:

  

• Sau sự kiện thứ hai, khán đài nhìn như sau:

  

• Sau sự kiện thứ ba, khán đài nhìn như sau:

  

• Sau sự kiện thứ sáu, khán đài nhìn như sau:

  

• Sau sự kiện thứ bảy, khán đài nhìn như sau:

  

Khi buổi biểu diễn đã hạ màn, khi Gấu Trắng đã hoàn thành tất cả thử thách, đã đi hết chặng đường của sự xứng đáng, từ sau cánh gà sân khấu mở ra một lối đi dẫn đến một cánh cửa bí ẩn, dẫn đến một căn phòng treo biển hiệu Giai Điệu Ngàn Năm. Đằng sau cánh cửa đó, chính là Quả Cầu Âm Thanh huyền thoại!

Để có thể tiến vào và giành lấy phần thưởng đỉnh cao cho sự xứng đáng đó, Gấu Trắng cần phải giải mã được Giai Điệu Ngàn Năm. Tuy nhiên, sau một hành trình dài đầy thử thách và chông gai, Gấu Trắng nhận ra rằng, Giai Điệu Ngàn Năm không chỉ đơn thuần là một bản nhạc cố định, mà đó chính là bản nhạc có ý nghĩa nhất với người muốn giải mã nó, là bản nhạc được biểu diễn bằng cả tâm huyết và trái tim.

Hãy giúp Gấu Trắng giải mã Giai Điệu Ngàn Năm và sở hữu Quả Cầu Âm Thanh nhé!

Input

Output

Giai Điệu Nằm Ngang!

Notes

Lưu ý: Bài tập này chỉ có duy nhất một test. Bài nộp của thí sinh sẽ là một trong hai loại file:

• File mã nguồn (C++, Python,...): mã nguồn này không đọc input, và sẽ in ra output là Giai Điệu Ngàn Năm.
• File TEXT (thí sinh xem trong mục "Gửi bài giải" ~\rightarrow~ chọn ngôn ngữ TEXT): thí sinh gõ trực tiếp đáp án của mình và nộp bài.