Mùa xuân về trên khắp nẻo đường, đất trời như khoác lên mình tấm áo mới rực rỡ. Tiết trời se lạnh dần tan biến, nhường chỗ cho những tia nắng ấm áp và hương hoa tràn ngập không gian. Trong không khí ấy, có một chàng sinh viên tên Tăng - vốn vừa lãng mạn, vừa có phần ngây thơ - đang ấp ủ một ước mơ nhỏ bé nhưng mãnh liệt: "một chuyến du xuân cùng người con gái mà anh thầm thương trộm nhớ bấy lâu".

Tăng không giàu có. Số tiền tiết kiệm từ việc làm thêm và sinh hoạt tằn tiện suốt năm qua chẳng đáng là bao. Nhưng tình cảm chân thành của anh thì lại rất lớn. Anh muốn dùng tất cả những gì mình có, không phải để tổ chức một chuyến đi xa hoa, mà là để tạo nên một hành trình giản dị nhưng trọn vẹn, một vòng tròn khép kín tượng trưng cho tình yêu không điểm bắt đầu và cũng chẳng có điểm kết thúc.

Thế nhưng, đời vốn dĩ chẳng dễ dàng. Khi tìm đến công ty lữ hành để xin thông tin, Tăng không nhận được danh sách tour sẵn có nào. Thay vào đó, nhân viên chỉ đưa cho anh một tấm bản đồ cũ kỹ, trên đó vẽ nên ~N~ thành phố và một số tuyến đường hai chiều nối chúng lại với nhau. Trên mỗi tuyến đường đều ghi rõ chi phí đi lại.

Anh bối rối nhìn tấm bản đồ, nhưng rồi chợt nghĩ: "Có lẽ, đây chính là thử thách mà số phận đặt ra cho mình. Nếu mình thật sự muốn ở bên cô ấy, mình phải tìm được một chuyến đi đẹp nhất - vừa tiết kiệm, vừa ý nghĩa, vừa đủ dài để có thật nhiều kỷ niệm."

Trong lòng Tăng, những tiêu chí cho chuyến hành trình đã hình thành rõ ràng:

1. Xuất phát từ một thành phố nào đó, và cuối cùng quay trở lại đúng thành phố ấy. Vì chỉ có như vậy, hành trình mới trở thành một vòng tròn hoàn hảo - vòng tròn mà anh ngầm ví như lời hẹn ước: tình yêu bắt đầu nơi đâu thì sẽ trở lại nơi đó, mãi mãi chẳng bao giờ lạc mất.

2. Mỗi thành phố đi qua chỉ được ghé một lần duy nhất, trừ thành phố xuất phát - nơi mà cả hành trình kết thúc, như trái tim Tăng, chỉ muốn một lần duy nhất thuộc về một người.

3. Hành trình phải ghé ít nhất ~K~ thành phố. Vì Tăng không muốn chuyến đi quá ngắn ngủi - tình yêu cần những kỷ niệm, cần những khoảng lặng, cần cả những đoạn đường dài để họ có thể đi bên nhau, chia sẻ và thấu hiểu.

4. Tổng chi phí phải là ít nhất có thể. Bởi chỉ khi tiết kiệm, Tăng mới có thể dành phần còn lại để mua một bó hoa tươi - gửi đến cô gái như lời tỏ tình chân thành nhất sau khi chuyến đi kết thúc.

Nếu tìm được hành trình như vậy, Tăng sẽ có thể trao cho cô ấy một mùa xuân trọn vẹn, một ký ức mà cả đời chẳng thể quên. Nếu không, anh chỉ biết ngồi bên cửa sổ, nhìn hoa đào rơi và tự nhủ: "Có lẽ mình phải đợi một mùa xuân khác..."

Input

• Dòng đầu tiên chứa ba số nguyên dương ~N, M, K~:
  • ~N~: số lượng thành phố. ~(N \leq 5000)~
  • ~M~: số lượng tuyến đường hai chiều trực tiếp nối giữa các thành phố. ~(M \leq 1000)~
  • ~K~: số lượng thành phố tối thiểu mà chuyến đi phải đi qua. ~(2 < K < N)~
• Tiếp theo là ~M~ dòng, mỗi dòng gồm ba số nguyên dương ~u, v, w~:
  • ~u, v~: hai thành phố được nối trực tiếp ~(1 \leq u, v \leq N)~.
  • ~w~: chi phí đi lại của tuyến đường đó ~(1 \leq w \leq 10^6)~.

Output

• Nếu tìm được chuyến đi thỏa mãn:
  • In ra hai dòng:
    • Dòng ~1~: số ~C~, là chi phí nhỏ nhất của chuyến đi.
    • Dòng ~2~: số lượng thành phố có trong chuyến đi.
• Nếu không tìm được, in ra: -1

Sample Input 1

5 6 3
1 4 1 
1 2 16
1 3 300
2 3 50
2 5 15
3 5 20

Sample Output 1

85
3

Sample Input 2

4 3 4
1 2 10
1 3 20
1 4 30

Sample Output 2

-1

Ràng buộc

• ~30\%~ số test có ~N \leq 25~.
• ~25\%~ số test có ~N \leq 50~.
• ~20\%~ số test có ~N \leq 100~.
• ~15\%~ số test có ~N \leq 1000~.
• ~10\%~ số test có ~N \leq 5000~.

Đêm trước kỳ thi Olympic Tin học sinh viên Việt Nam, thành phố vẫn sáng đèn, nhưng trong căn phòng nhỏ màu hường với những chú gấu bông màu hồng nơi góc phố cũ, Tăng vẫn còn ngồi trước màn hình laptop đã sờn phím. Tiếng mưa ngoài hiên nhỏ xuống từng nhịp đều, hòa vào tiếng gõ bàn phím khẽ khàng - một thứ âm thanh cô độc nhưng cũng đầy kiên định.

Đối với nhiều người, Olympic chỉ là một kỳ thi. Nhưng với Tăng, nó giống như một lời hứa với chính mình - rằng dù giàu có, dù chẳng có ai kề bên, anh vẫn có thể vươn tới những điều lớn lao bằng trí tuệ và lòng bền bỉ.

Hôm nay, anh gặp một bài toán kỳ lạ. Một bài toán mà khi đọc qua, Tăng lại cảm thấy có gì đó rất… quen thuộc. Có lẽ vì nó giống hệt với cuộc sống của anh - một chuỗi những đoạn đường ngắn ngủi nhưng chứa đầy mâu thuẫn, giữa chẵn và lẻ, giữa lý trí và cảm xúc, giữa ước mơ và thực tại.

Trên màn hình là một dãy số ~A~ gồm ~N~ số nguyên dương - giống như chuỗi ngày tháng nối tiếp nhau trong đời người. Người ta định nghĩa một dãy con liên tiếp của ~A~ là đẹp, nếu như trong dãy đó:

• Có ít nhất một số chẵn và ít nhất một số lẻ - bởi vì, như cuộc sống, chỉ khi có cả vui và buồn, con người mới trưởng thành.
• Gọi ~X~ là tổng các phần tử chẵn, ~Y~ là tổng các phần tử lẻ trong dãy con đó, thì ~0 ≤ X - Y ≤ K~ - nghĩa là, dù lý trí có mạnh mẽ đến đâu, cảm xúc cũng không được cách quá xa. Sự cân bằng ấy làm nên cái đẹp.

Tăng đọc đề, và trong đầu anh hiện lên hình ảnh của chính mình: một người đã trải qua bao cung bậc cảm xúc, cố gắng giữ cho trái tim mình không quá lạnh, nhưng cũng không quá yếu mềm. Giờ đây, bài toán không chỉ là con số, mà là hành trình tìm lại sự hài hòa giữa hai nửa trong anh - nửa "chẵn" lý trí, và nửa "lẻ" đầy cảm xúc.

Yêu cầu: Hãy giúp Tăng tìm xem có bao nhiêu dãy con đẹp trong dãy số ~A~.

Input

• Dòng đầu tiên: chứa hai số nguyên dương ~N~ và ~K~. ~(N \le 2\times 10^5; K \le 10^6)~
• Dòng thứ hai: chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^6)~.

Output

• In ra một số nguyên duy nhất - số lượng dãy con đẹp của dãy số ~A~.

Sample Input 1

5 5
1 3 2 9 10

Sample Output 1

3

Sample Input 2

5 3
1 1 1 1 20

Sample Output 2

0

Ràng buộc

• ~20\%~ số test có ~N \le 200~
• ~20\%~ số test có ~N \le 2000~
• ~20\%~ số test có ~K = 0~
• ~20\%~ số test có ~K \le 100~
• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Tháng mười hai, trời Đà Lạt vẫn còn lất phất những cơn mưa mỏng, như ai đó đang giấu đi nước mắt của mình trong sương. Tăng ngồi bên khung cửa gỗ cũ, đôi mắt nhìn xa xăm qua lớp hơi nước đọng trên kính, nơi những ánh đèn vàng phản chiếu mờ ảo. Cạnh anh là chiếc laptop đã cũ, màn hình sáng nhẹ, dòng chữ nhấp nháy của một bài toán chưa hoàn thành.

Trên bàn, có một tấm ảnh đã nhòe màu đó là tấm hình duy nhất của người con gái từng đi bên anh suốt những ngày tuổi trẻ. Họ từng cùng nhau ngồi giải những bài toán khó, từng thức trắng đêm trước kỳ thi, từng hứa rằng sẽ cùng đi đến cuối con đường. Nhưng rồi, giống như những con số biến mất khi xóa dòng code, em đã rời xa - nhẹ nhàng, mà vẫn khiến lòng Tăng như đổ sập.

Anh mở lại những file cũ, và bất ngờ thấy một bài tập mà em từng viết nửa chừng. Trên đó, chỉ có vài dòng ghi chú, nguệch ngoạc như vội:

"Dãy số ~A~ gồm ~N~ phần tử. Với mỗi ~K~, hãy tìm đoạn dài nhất... nơi mọi thứ vẫn chưa vượt quá giới hạn của mình.""

Tăng mỉm cười buồn. Em khi ấy luôn thích ví von những con số như cảm xúc - khi ta yêu ai quá nhiều, chính là lúc cảm xúc vượt ngưỡng, và mọi thứ tan vỡ. Có lẽ, ~K~ chính là giới hạn mà con người có thể chịu đựng được - vượt qua nó, mọi thứ sẽ không còn nguyên vẹn nữa.

Dãy số ~A~ vẫn nằm đó, im lặng trên màn hình như một dòng ký ức bất tận:

• Dãy số ~A~ gồm các giá trị ~a_1, a_2, ..., a_N~, còn với Tăng đây lại là những mảnh vụn ký ức về những ngày bên em.
• Có những giá trị âm được Tăng xem như những lần cãi vã, những tổn thương, những đêm mưa buồn.
• Có giá trị dương như những phút vui vẻ hạnh phúc, những buổi cà phê sớm, những chiều dạo hồ, tiếng cười trong trẻo.

Giờ đây, Tăng được trao một con số ~K~, và anh tự hỏi:

"Liệu trong chuỗi ký ức ấy, đoạn dài nhất mà anh vẫn có thể chịu đựng - không để bất kỳ cảm xúc nào vượt quá ngưỡng K - sẽ dài đến đâu?""

Và thế là anh lại gõ, từng dòng, từng dòng... Như thể đang lần tìm lại ranh giới giữa nỗi nhớ và sự chịu đựng, giữa những gì còn có thể giữ và những gì buộc phải buông.

Cuối cùng đến lúc đêm xuống. Tăng sau khi đã hoàn thành những dòng code, anh khẽ nhấn Enter, và chương trình chạy. Những con số lần lượt hiện ra - gọn gàng, lạnh lùng, nhưng đối với anh, đó là câu trả lời cho một nỗi nhớ. Anh không còn gặp em nữa. Nhưng mỗi lần gõ code, mỗi lần nhìn vào những dãy số, anh vẫn thấy dáng người con gái ấy mỉm cười - trong một đoạn con liên tiếp nhưng không bao giờ đứt, nằm mãi trong trái tim anh. 💔

Input

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ - tương ứng với độ dài của dãy ký ức và số lần Tăng tự vấn lòng mình. ~(N, Q \le 10^5)~
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, …, a_N~ - những mảnh ký ức được ghi lại bằng con số. ~(|a_i| \le 10^9)~
• Tiếp theo là ~Q~ dòng, mỗi dòng chứa một số nguyên ~K~, tượng trưng cho giới hạn cảm xúc mà Tăng có thể chịu đựng ở mỗi lần hồi tưởng. ~(|K| \le 10^9)~

Output

• Với mỗi truy vấn, in ra một số nguyên duy nhất - độ dài của dãy con liên tiếp dài nhất trong ký ức, nơi mọi cảm xúc (mọi giá trị ~a_i~) đều không vượt quá ~K~.

Sample Input

6 4
-2 5 6 10 -5 0
-10
5
-4
11

Sample Output

0
2
1
6

Ràng buộc

• ~20\%~ test có ~N, Q \le 5\times 10^3~
• ~20\%~ test có ~a_1 \le a_2 \le ... \le a_{N-1} \le a_N~
• ~20\%~ test có ~a_1 \ge a_2 \ge ... \ge a_{N-1} \ge a_N~
• ~20\%~ test có ~a_1 \ge a_2 \ge ... \le a_{N-1} \le a_N~
• ~20\%~ test cuối cùng không có ràng buộc gì thêm.

Tăng chưa bao giờ nghĩ rằng, việc nhớ một người mới quen lại có thể khiến tim mình hỗn độn đến thế. Mọi thứ đến nhanh - tin nhắn đầu tiên, nụ cười vụng về, những lần gặp gỡ lúng túng, và cả ánh mắt khiến cậu chẳng thể rời đi.

Rồi một buổi chiều yên tĩnh ở Trường đại học quốc tế Miền Đông, trước kỳ thi Olympic Tin học sinh viên 2025, khi ngồi giữa những trang giấy trắng và dãy số dài, Tăng chợt nhận ra... ký ức về cô ấy cũng giống như những con số. Chúng rối tung và chưa theo trật tự nào, nhưng nếu cậu có thể sắp xếp chúng một cách đúng đắn - có lẽ mọi thứ sẽ trở nên dễ chịu hơn, như cách ta xếp lại những ngăn tủ trong lòng mình.

Cậu tưởng tượng ra một hệ thống kho ký ức - nơi mỗi kỷ niệm được đặt trong một chiếc hộp nhỏ, đánh số từ ~1~ đến ~N~. Mỗi hộp chứa đúng một "vật thể" mang giá trị cảm xúc của nó - có thể là nụ cười đầu tiên ~A_1~, tin nhắn tối hôm qua ~A_2~, hay khoảnh khắc em khẽ quay lại nhìn ~A_3,...~ . Tất cả các giá trị đó đều độc nhất, không có ký ức nào trùng với ký ức nào.

Tăng được biết rằng, giữa mỗi cặp kho liền kề ~i~ và ~i + 1~, tồn tại một chi phí ~C_i~ - đó là cái giá mà Tăng phải trả nếu muốn chuyển ký ức từ vị trí này sang vị trí kia, như thể mỗi lần muốn sắp xếp lại lòng mình, cậu đều phải đánh đổi chút bình yên.

Tăng được giao một nhiệm vụ - cũng là một phép thử của cảm xúc:

• Sắp xếp lại tất cả ký ức ấy sao cho chúng được đặt thành một dãy không giảm về giá trị, tức là những điều nhỏ bé, dịu dàng sẽ dần dần dẫn đến những điều lớn lao, sâu sắc hơn.
• Khi sắp xếp xong, mỗi kho phải chứa đúng một vật thể, không được bỏ sót, không được chồng chéo.
• Và điều mà Tăng mong muốn nhất là tổng chi phí cảm xúc - tức tổng chi phí di chuyển khi sắp xếp các vật thể phải nhỏ nhất có thể.

Nhưng mọi thứ không đứng yên mãi. Giống như cảm xúc của con người, hệ thống ký ức ấy cũng thay đổi theo thời gian. Trong suốt quá trình "chơi", hay có lẽ là trong quá trình "nhớ", Tăng sẽ nhận được ~Q~ truy vấn - như những sự kiện nhỏ diễn ra trong mối quan hệ:

• Có khi, hai kho ký ức bị hoán đổi – như khi ta bất chợt thấy thứ từng mờ nhạt trở nên rõ ràng hơn.
• Có khi, chi phí để di chuyển giữa hai kho thay đổi – như khi khoảng cách giữa hai trái tim trở nên xa hơn hay gần lại.

Sau mỗi thay đổi ấy, Tăng lại phải tính toán lại tổng chi phí cảm xúc ít nhất nếu muốn sắp xếp lại mọi thứ cho ổn thỏa. Cứ thế, mỗi truy vấn là một nhịp tim khác nhau, mỗi lần sắp xếp lại là một lần Tăng học cách đối diện với chính mình.

Input

• Dòng đầu tiên: chứa một số nguyên duy nhất ~N~ ~(2 \le N \le 2 \times 10^5)~ - số lượng kho ký ức.
• Dòng thứ hai: chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~` ~(1 \le A_i \le 10^9)~, là giá trị cảm xúc ban đầu trong từng kho. Các giá trị này đôi một khác nhau.
• Dòng thứ ba: chứa ~N - 1~ số nguyên ~C_1, C_2,..., C_{N-1}~ ~(1 \le C_i \le 10^5)~, là chi phí cảm xúc khi chuyển giữa hai kho ký ức liên tiếp.
• Dòng thứ tư: chứa một số nguyên ~Q~ ~(0 ≤ Q ≤ 2 \times 10^5)~ - số lượng thay đổi mà hệ thống sẽ gửi đến.
• Tiếp theo là ~Q~ dòng, mỗi dòng mô tả một truy vấn:
  • ~1~ ~x~ ~y~: Hoán đổi giá trị của hai vật thể ở kho ~x~ và ~y~ ~(1 \le x, y \le N, x ≠ y)~.
  • ~2~ ~p~ ~v~: Cập nhật lại chi phí di chuyển giữa kho ~p~ và kho ~p + 1~ thành ~v~ ~(1 \le p < N; 1 \le v \le 10^5)~.

Output

• Gồm ~Q + 1~ dòng:
  • Dòng đầu tiên in ra tổng chi phí sắp xếp trong trạng thái ban đầu (trước khi có truy vấn).
  • Mỗi dòng tiếp theo in ra tổng chi phí sắp xếp tối thiểu sau khi thực hiện từng truy vấn tương ứng.

Sample Input

3
1 3 2
1 2
2
2 2 3
1 2 3

Sample Output

4
6
0

Giải thích

• Ban đầu, các kho ký ức có thứ tự là ~(1, 3, 2)~ - mọi thứ chưa sẵn sàng, còn rối rắm. Để sắp xếp lại sao cho mạch cảm xúc dần tăng ~(1, 2, 3)~, Tăng cần di chuyển ký ức ~3~ qua một đoạn chi phí ~2~, rồi lại đưa ~2~ trở lại chỗ cũ - tổng chi phí là ~4~.
• Khi khoảng cách giữa hai kho thay đổi (chi phí ~C_2~ tăng lên thành ~3~), việc nhớ lại trở nên khó hơn - chi phí cảm xúc tăng lên thành ~6~.
• Cuối cùng, khi Tăng hoán đổi vị trí hai ký ức (như thể trong lòng cậu mọi thứ đã tự nhiên trở về đúng vị trí của nó), dãy trở nên hoàn hảo - ~(1, 2, 3)~. Và lúc ấy, tổng chi phí cảm xúc là ~0~. Một trạng thái yên bình hiếm hoi - như thể sau bao nhiêu rối ren, trái tim cuối cùng cũng biết sắp xếp lại chính mình.

Ràng buộc

• Subtask ~1~ ~(25\%)~: ~N, Q \le 200~.
• Subtask ~2~ ~(20\%)~: ~N, Q \le 5000~, chỉ có truy vấn loại ~2~.
• Subtask ~3~ ~(20\%)~: ~N, Q \le 5000~.
• Subtask ~4~ ~(20\%)~: chỉ có truy vấn loại ~2~.
• Subtask ~5~ ~(15\%)~: không có ràng buộc gì thêm.