Cho một dãy ~A~ độ dài ~n~, gồm các số nguyên dương ~A_1, A_2, ..., A_n~. Một dãy số được coi là đẹp nếu như các vị trí ~i~ chẵn thì ~A_i~ là số chẵn và các vị trí ~i~ lẻ thì ~A_i~ là số lẻ. Hãy tính số phép swap nhỏ nhất để ~A~ trở thành dãy đẹp. Một phép swap là phép đổi chỗ hai phần tử liên tiếp của dãy ~A~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n (n \le 10^6)~, là độ dài của dãy.

• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le n)~.

Output

• Một số nguyên duy nhất là số phép swap nhỏ nhất cần để A trở thành dãy đẹp. Nếu không tồn tại cách swap, in ra -1.

Sample Input 1

6
6 5 4 3 2 1

Sample Output 1

3

Note

• Có ~50\%~ số test thoả mãn ~n \le 20~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Cho một chuỗi ~s~ bao gồm các chữ cái tiếng Anh viết thường. Cho ~q~ truy vấn, chọn hai số nguyên ~l~ và ~r~, lấy chuỗi con ~s_{l...r}~ (chuỗi con của ~s~ từ chỉ mục ~l~ tới chỉ mục ~r~).

Hãy xem xét tất cả các palindrome có thể được tạo ra từ một số chữ cái từ chuỗi con ~s_{l...r}~ . Bạn có thể sắp xếp lại các chữ cái khi bạn cần. Một số palindrome này có chiều dài tối đa trong số tất cả các palindrome này.

Hai xâu palindrome được coi là khác nhau nếu độ dài khác nhau hoặc tồn tại ít nhất một vị trí khác nhau.

Yêu cầu: Hãy tìm ra có bao nhiêu chuỗi palindrome có độ dài tối đa?

Input

• Dòng đầu tiên chứa chuỗi ~s~ (~1 \le |s| \le 10^5~).

• Dòng thứ hai chứa một số nguyên ~q~ (~1 \le q \le 10^5~).

• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách ~l_i, r_i~ (~1 \le l_i \le r_i \le |s|~), biểu thị cho giá trị ~l~ và ~r~ trong truy vấn thứ ~i~.

Output

• Đối với mỗi truy vấn, in ra một dòng chứa một số nguyên biểu thị câu trả lời. Vì kết quả có thể rất lớn, in phần dư khi lấy kết quả chia cho ~10^9 + 7~.

Subtask

• ~30\%~ số test có ~1 \le |s| \le 100, 1 \le q \le 1000, r_i - l_i \le 3~.

• ~30\%~ số test khác có ~1 \le |s| \le 100, 1 \le q \le 1000~.

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

hello
2
2 5
3 4

Sample Output 1

2
1

Sample Input 2

bedaocontest
1
5 7

Sample Output 2

1

Note

Ở test ví dụ thứ nhất:

• Truy vấn thứ nhất có ~2~ xâu palindrome dài nhất thỏa mãn là: lol và lel.

• Truy vấn thứ 2 có ~1~ xâu palindrome dài nhất thỏa mãn là: ll.

Ở test ví dụ thứ hai:

• Truy vấn thứ nhất có ~1~ xâu palindrome dài nhất thỏa mãn là: oco.

Trung cần xây dựng một hàng rào có độ dài ~m~.

Tổ tiên Trung truyền lại cho cậu một thanh gỗ có độ dài vô tận để xây hàng rào. Cậu sẽ chặt thanh gỗ này thành ~m~ thanh gỗ ngắn hơn với độ rộng như nhau và độ cao là một số nguyên dương không lớn hơn ~n~.

Gọi ~h_i~ là độ cao của thanh gỗ ở vị trí ~i~, Trung cần xây dựng một hàng rào đẹp thỏa mãn các tính chất sau:

• ~h_1~ có thể nhận một giá trị bất kì.

• Nếu ~2 \cdot h_i > n~, ~h_{i+1}~ có thể nhận giá trị bất kì.

• Nếu ~2 \cdot h_i \le n~, ~h_{i+1} \ge 2 \cdot h_i~.

• ~2 \cdot h_m > n~.

Giúp Trung tính số lượng hàng rào đẹp có thể xây dựng, chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~T~ (~1\le T \le 10^5~) - số test cases cần xử lý.

• ~T~ dòng tiếp theo mỗi dòng gồm hai số nguyên dương ~n, m~ là độ cao tối đa và số thanh gỗ cần để xây dựng hàng rào.

Tổng ~n~ trong ~T~ test cases không vượt quá ~10^5~.

Tổng ~m~ trong ~T~ test cases không vượt quá ~5\times 10^5~.

Output

• Gồm ~T~ dòng, mỗi dòng là kết quả của một test case.

Subtask

Subtask ~1~ (~20~ điểm): ~n,m\le 300~.

Subtask ~2~ (~30~ điểm): ~n,m\le 3000~.

Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

5
1 2
2 2
3 4
5 6
10 10

Sample Output 1

1
2
44
4629
564985327

Cho một đồ thị vô hướng liên thông có trọng số ~n~ đỉnh, ~m~ cạnh. Cạnh thứ ~i~ có trọng số là ~weight(i)~. Định nghĩa cost của 1 đường đi qua các cạnh ~e_1, e_2, ..., e_k~ là:

~k \times X + \sum_{i=1}^{k} weight(e_i) - max(weight(e_1), ..., weight(e_k)) + min(weight(e_1), ..., weight(e_k))~.

Tìm đường đi có cost nhỏ nhất từ ~S~ đến ~n - 1~ đỉnh còn lại.

Input

• Dòng đầu tiên ~4~ số nguyên ~n, m, S, X~ ~(1 \le n, m \le 2 \times 10^5, 1 \le S \le n, 1 \le X \le 10^9)~.

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~u,v,w~ lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~ ~(1 \le u, v \le n, u \ne v, 1 \le w \le 10^9)~.

Output

• In ra ~n - 1~ số nguyên là kết quả cần tìm. Các khoảng cách được in theo thứ tự đỉnh tăng dần.

Subtask

• ~20\%~ số test có ~1 \le n, m \le 10~.

• ~20\%~ số test khác có ~1 \le n, m \le 100~.

• ~20\%~ số test khác có ~m = n~.

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

7 9 7

Một lớp học nọ ở thị trấn bedao có ~n~ học sinh, mỗi học sinh có chỉ số tốt bụng là ~a_i~. Lớp học được dẫn dắt bởi lớp trưởng lastPledge. Mặc dù ăn ở khá tốt tuy nhiên lastPledge vẫn không vừa lòng được cô giáo chủ nhiệm. Chính vì vậy, trong ~q~ ngày tới, mỗi ngày cô giáo sẽ giao cho lastPledge một nhiệm vụ. Mỗi nhiệm vụ cô giáo giao sẽ thuộc ~1~ trong ~2~ loại sau:

• 1 i x: lastPledge cần thay đổi chỉ số tốt bụng của bạn học sinh thứ ~i~ thành ~x~.

• 2 l r: lastPledge cần tìm giá trị trả về của đoạn code sau:

  play(l, r):
      k = a[l]
      i = l + 1
      while i < r:
          k = median(k, a[i], a[i + 1])
          i = i + 2
      return k
  

  với ~\text{median}(x,y,z)~ là số nằm giữa trong ba số ~x,y,z~.

Đây là một nhiệm vụ khó khăn dành cho lastPledge, vì vậy lastPledge cần sự giúp đỡ của các cao nhân để giải bài toán này. Hãy giúp lastPledge nhé!

Input

• Dòng đầu gồm ~2~ số nguyên ~n~ và ~q~ ~(1 \le n,q \le 10^6)~.

• Dòng tiếp theo gồm ~n~ số nguyên ~a_1,a_2,\ldots, a_n \ (1 \le a_i \le 10^9)~.

• ~q~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên thể hiện cho nhiệm vụ loại ~1~ hoặc loại ~2~. Với nhiệm vụ loại ~1~ thì ~1 \le i \le n, 1 \le x \le 10^9~, loại ~2~ thì ~1 \le l \le r \le n~.

Output

• Với mỗi nhiệm vụ loại ~2~, in ra trên mỗi dòng là giá trị trả về của nhiệm vụ đó.

Subtask

• ~50\%~ số test khác có ~n, q \le 10^5~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

3
4
3

Đất nước XYZ có ~N~ thành phố được đánh số từ ~1~ đến ~N~, thủ đô được đánh số ~1~. Mạng lưới điện ở XYZ bao gồm ~N-1~ đường dây truyền tải được đánh số từ ~1~ đến ~N-1~. Đường dây thứ ~i~ kết nối hai thành phố ~u_i~ với thành phố ~v_i~ và có độ dài là ~w_i~. Mạng lưới đảm bảo rằng điện có thể được truyển tải giữa bất kì cặp thành phố nào một cách trực tiếp hoặc gián tiếp qua các thành phố khác. Người ta ước tính rằng thành phố ~u~ cần được cung cấp một lượng điện là ~a_u~ đơn vị. Lượng điện thất thoát khi truyền tải được tính theo công thức ~A=X\cdot d~, với X và ~d~ là lượng điện và khoảng cách đã truyền tải.

Chính quyền đang có kế hoạch xây dựng một số nhà máy điện ở một trong ~N~ thành phố. Để tiết kiệm chi phí, chính quyền cần tìm thành phố ~u~ sao cho tối thiểu hóa tổng lượng điện thất thoát ~S=\displaystyle\sum_{v=1}^N a(v)\cdot d(u,v)~ với ~d(u,v)~ là khoảng cách từ thành phố ~u~ đến thành phố ~v~.

Để tìm vị trí xây nhà máy điện tối ưu, chính quyền sẽ quan sát nhu cầu điện của ~N~ thành phố. Có một dãy ~Q~ các thay đổi trong nhu cầu, mỗi thay đổi nằm trong bốn loại sau:

• 1 u k: Nhu cầu của thành phố ~u~ tăng lên ~k~ đơn vị.

• 2 u k: Nhu cầu của thành phố ~u~ giảm xuống ~k~ đơn vị.

• 3 u k: Với mỗi thành phố ~v~ được quản lý bởi ~u~, nhu cầu của ~v~ tăng lên ~k~ đơn vị.

• 4 u k: Với mỗi thành phố ~v~ được quản lý bởi ~u~, nhu cầu của ~v~ giảm đi ~k~ đơn vị.

Ở đây ta nói ~v~ được quản lý bởi ~u~ nếu đường đi từ ~v~ đến thủ đô phải đi qua ~u~.

Yêu cầu: Sau mỗi thay đổi, hãy tìm thành phố tối ưu để xây nhà máy điện.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~Q~ (~1\le N,Q\le 2\cdot 10^5~).

• ~N-1~ dòng tiếp theo mô tả ~N-1~ đường dây truyền tải với ba số nguyên ~u_i,v_i,w_i~ (~w_i\le 10^7~).

• Dòng tiếp theo gồm ~n~ số nguyên ~a_1,a_2,\ldots,a_n~ (~0\le a_i\le 10^7~).

• ~Q~ dòng cuối cùng mô tả thông tin về ~Q~ sự thay đổi thuộc 1 trong 4 loại đã nêu với ba số nguyên ~t_j,u_j,k_j~ (~1\le t_j\le 4, k_j\le 10^7~). Dữ liệu đảm bảo nhu cầu của mỗi thành phố luôn không âm sau mỗi thay đổi.

Output

• Với mỗi sự thay đổi in ra thành phố tối ưu trên một dòng. Nếu có nhiều đáp án, bạn có thể đưa ra bất kì trong số chúng.

Subtask

• ~6\%~ số test thỏa mãn ~N\le 100, Q\le 5000~.

• ~10\%~ số test thỏa mãn ~N\le 5000, Q\le 5000~.

• ~12\%~ số test thỏa mãn mạng lưới điện có dạng đường thẳng.

• ~16\%~ số test thỏa mãn chỉ có các sự thay đổi loại ~1~.

• ~20\%~ số test thỏa mãn chỉ có các sự thay đổi loại ~1~ và ~2~.

• ~36\%~ số test không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

1
2
1