Q Từng hỏi C rằng cậu có biết loài hoa mà tớ thích nhất không?
C: Hmmm hoa hướng dương chăng, vì nó rực rỡ như cậu vậy
Q: Hay vậy cậu đoán đúng rồi nhưng mà nó phải thỏa mãn một số điều kiện sau cơ:

Ở ngọn đồi nơi mà C và Q sinh sống có ~n~ bông hoa hướng dương và các hoa có số cánh hoa là ~a_i~ với ~1 \le i \le n~. Vì rất thích người bạn của mình nên C quyết định thu thập ba bông hoa ~i, j, k~ để tặng cho cậu ấy, sao cho ba bông hoa ấy thỏa mãn các điều kiện sau:

• ~a_i < a_j < a_k < a_i + a_j.~

• ~19a_i+19a_j+6a_k~ chia hết cho ~7~ hoặc ~6~.

Biết rằng độ rực rỡ của bó hoa được tính bằng: ~a_i+a_j-a_k.~

Hãy tính TÍCH độ rực rỡ của các bó hoa mà C có thể thu thập được. Nếu không thu thập được bó hoa nào hãy in ra ~0~. biết rằng điều này sẽ khiến C buồn :<

Input:

• Dòng đầu tiên gồm một số nguyên ~N~ với ~1 \le N \le 10^5~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ với ~1 \le a_i \le 3 \cdot 10^3~.

Output:

TÍCH độ rực rỡ các bộ ba ~(i,j,k)~ thỏa mãn điều kiện và MOD cho ~10^9+7~.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

1

Sample Input 2

5
1 3 7 6 2

Sample Output 2

0

Giải thích

Trong VD1, các bộ thỏa mãn sẽ là ~(2,3,4),(2,4,5)~ và đều có cùng độ rực rỡ là ~1~, vì thế đáp số là ~1^2 = 1.~ Còn trong VD2, C đã không có bó hoa nào và bạn ấy buồn lắm.

---

Bạn biết không, ở ngọn đồi đó làm gì mà có hoa hướng dương...

" " "
C: Cố lên, cố lên cậu làm được mà
Q: Nhất định ạ!!
C: Không sao mà có tớ đây rồi
C: Cố lên
" " "

Vẫn như mọi hôm thôi, sau khi hoàn thành hết mọi công việc, C lại chạy qua nhà Q để cùng cậu ấy đi chơi trên những ngọn đồi. Nhưng đáng tiếc thay hôm nay, Q lại gặp phải một vấn đề khó khăn do chính cô tạo ra. Được biết rằng bằng sự tinh nghịch của mình, Q đã làm hỏng một vách tường ở nhà cô ấy, vì vậy để bù đắp cho lỗi lầm của mình thì cô phải sửa vách tường để có thể được mẹ cho đi chơi.

Biết rằng Q đã phá hỏng một vách tường hình chữ nhật kích thước ~M \times N~. Để sửa chữa vách tường, Q cần sử dụng những miếng gỗ có kích thước ~1 \times 2~ và tất nhiên C có thể xoay chúng ngang hoặc dọc và lắp lên trên vách tường. Q rất cần sự giúp đỡ của C để tìm ra số cách khác nhau để lắp đầy vách tường bằng những miếng gỗ này. C đã quá mệt sau khi chạy một một mạch đến nhà cậu ấy (do lười vận động) và vì vậy cậu ấy yêu cầu bạn giúp cậu ấy tính toán bài toán này. Bạn hãy cung cấp thông tin để C có thể chỉ cho Q cách lắp đặt tối ưu và nhanh nhất, để hai người có thể đi chơi cùng nhau.

Quy ước rằng hai cách lắp được gọi là khác nhau nếu tồn tại ít nhất một ô để trong một cách nó được phủ bởi miếng gỗ đặt ngang và trong cách lắp kia được phủ bởi miếng gỗ đặt dọc.

Input:

Chỉ gồm hai số nguyên ~N, M~ với ~1 \le N, M \le 10.~

Output:

Đáp số cho bài toán.

Sample Input 1

2 2

Sample Output 1

2

Sample Input 2

2 3

Sample Output 2

3

Giải thích

Trong VD1, ta có thể xếp ~2~ viên gạch nằm dọc hoặc ~2~ viên gạch nằm ngang, có tất cả ~2~ cách; còn trong VD2, ta có thể xếp ~3~ gạch nằm dọc hoặc ~2~ ngang, ~1~ dọc hoặc ~1~ dọc, ~2~ ngang, có tất cả ~3~ cách.

---

" " "
Q: Này này tại sao học bài lại phải im lặng vậy chứ?
Q: Tớ ghét sự tĩnh lặng :<
C: Hmmmm
Q: Đây để tớ hát cho cậu nghe kkk :>
" " "

tiếng ghi-ta nâu
bầu trời cô gái ấy
tiếng ghi-ta lá xanh biết mấy
tiếng ghi-ta tròn bọt nước vỡ tan
tiếng ghi-ta ròng ròng
máu chảy

không ai chôn cất tiếng đàn
tiếng đàn như cỏ mọc hoang
giọt nước mắt vầng trăng
long lanh trong đáy giếng

đường chỉ tay đã đứt
dòng sông rộng vô cùng
Lorca bơi sang ngang
trên chiếc ghi-ta màu bạc

chàng ném lá bùa cô gái di-gan
vào xoáy nước
chàng ném trái tim mình
vào lặng yên bất chợt

li-la li-la li-la...

Một ngày nọ Q và C cùng nhau tìm hiểu về một tác phẩm văn học, ở nơi họ sinh sống văn học và chữ nghĩa vốn là một thứ xa xỉ mà ai cũng ao ước. Khát khao của hai người là học thật nhiều tri thức để có thể thay đổi thực tại của bản thân, trong trí nhớ của C thì tác phẩm cậu đọc được khi đó tồn tại một thanh âm ngân vang (có lẻ là tác phẩm trên) vì vậy cậu nôn nóng học thật nhanh để có thể đọc cho Q nghe. Sau khi học xong cậu nhanh chóng ghi ra giấy những gì mình đã học, thứ cậu ghi lên tờ giấy là một xâu S có độ dài là N để tiện cho việc xem lại. Nhưng thật chớ trêu thay cậu lại rất hay viết sai chính tả.....

Sau bao quá trình học tập C biết rằng mình thường viết sai chính tả một số chữ cái trong bảng chữ cái. Vì vậy cậu tự hỏi là mình đã ghi sai những gì trong chuỗi mình đã tự ghi ra. Nhưng vì ở gần Q một thời gian nên cậu cũng bị lây tính lười nên C quyết định giao việc này lại cho bạn.

C cung cấp cho bạn một mảng nhị phân ~a~ gồm ~26~ phần tử và một số ~K~, trong đó ~a_i~ với ~1 \le i \le 26~ chỉ mang hai giá là ~1~ hoặc ~0~ nghĩa là chữ cái thứ ~i~ trong bảng chữ cái mà C luôn ghi đúng và ngược lại.

Nhiệm vụ của bạn là hãy giúp C đếm xem có bao nhiêu xâu con riêng biệt mà số lượng chữ cái C ghi sai trong xâu con đó không được vượt quá ~K.~

Input:

• Dòng đầu tiên gồm một xâu ~S~ gồm các chữ cái tiếng anh viết thường có độ dài là ~N~ với ~1 \le N \le 2000.~

• Dòng thứ hai là mảng nhị phân ~a~ gồm ~26~ phần tử, trong đó ~a_i~ bằng ~1~ nghĩa là chữ cái thứ ~i~ trong bảng chữ cái mà C luôn viết đúng và ngược lại.

• Dòng thứ ba là số nguyên ~K~ với ~0 \le K \le N.~

Output

Đáp số của bài toán.

Sample Input 1

aaaaa
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1

Sample Output 1

5

Sample Input 2

tocacaumuoi
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0

Sample Output 2

61

Giải thích

Trong VD1, các xâu thỏa mãn sẽ là

• a
• aa
• aaa
• aaaa
• aaaaa

---

Bạn có thắc mắc vì sao xâu S lại chỉ gồm các ký tự tiếng anh viết thường không?

Vì tác phẩm trên là tiếng đàn ghita của lorca

"Này này dậy thôi, dậy thôi, cùng dậy đón bình minh nào!!
Lười lắm, lười lắm tớ không đi đâu
Một là đi, hai là vĩnh viễn nằm đó luôn!! =)))"

~

Ở nơi Q và C ở có ~N~ ngọn núi khác nhau. Mỗi ngọn núi có một độ cao là ~a_i~ và các ngọn núi này tạo thành một dãy núi lớn, cao kinh khủng. Để có thể đón được ánh bình minh tuyệt đẹp, Q đã quyết định thức thật sớm và băng qua dãy núi mặc dù việc này rất là mệt mỗi cho một con người lười vận động như C. Nhưng C cũng đâu còn lựa chọn nào khác ngoài việc là cố hết mình và leo cùng cậu ấy @_@

Trong quá trình đi, C tự hỏi liệu mình có đủ sức để băng qua dãy núi không? Cậu tự trả lời câu hỏi này bằng cách tính chênh lệch độ cao của ngọn núi cao nhất và thấp nhất trong quá trình đi và so với thể lực của mình. Nhưng cậu biết một việc còn đáng sợ hơn thế nhiều, đó là cậu không biết C sẽ dừng lại ở ngọn núi nào để ngắm bình minh. Vì vậy, hãy giúp cậu ấy tính tổng độ chênh lệch của ngọn núi cao nhất và thấp nhất trong tất cả dãy núi con và bảo rằng cậu có thể làm được, chayyooo!! Biết rằng một dãy núi con là một dãy các ngọn núi liền kề và không có dãy nào không có núi.

Cảnh tượng mà cả hai đã được ngắm nhìn khi đó, có lẽ họ sẽ không bao giờ có thể quên được. Cảm ơn vì sự giúp đỡ của bạn :>

Input:

• Dòng đầu tiên gồm một số nguyên ~N~ số lượng ngọn núi trong dãy núi với ~1 \le N \le 4 \cdot 10^5.~

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ là độ cao các ngọn núi ~0 \le a_i \le 10^9.~

Output:

Đáp số của bài toán.

Sample Input

4
0 1 0 6

Sample Output

21

Giải thích

• Dãy {0} có độ chênh lệch là: ~0~
• Dãy {1} có độ chênh lệch là: ~0~
• Dãy {0} có độ chênh lệch là: ~0~
• Dãy {6} có độ chênh lệch là: ~0~
• Dãy {0, 1} có độ chênh lệch là: ~1~
• Dãy {1, 0} có độ chênh lệch là: ~1~
• Dãy {0, 6} có độ chênh lệch là: ~6~
• Dãy {0, 1, 0} có độ chênh lệch là: ~1~
• Dãy {1, 0, 6} có độ chênh lệch là: ~6~
• Dãy {0, 1, 0, 6} có độ chênh lệch là: ~6~
• Nên tổng các độ chênh lệch là: ~21.~

---

"Cậu biết không mỗi khi thức dậy vào rạng sáng tớ vẫn thấy ánh bình minh quen thuộc như ngày nào.
Chỉ là không gian và thời gian lúc này không còn quen thuộc như ngày xưa nữa.
Không biết ở nơi đó cậu có đang thấy ánh bình minh mà tớ vẫn luôn nhìn về, từ những ngày ban đầu không?"

Có một câu chuyện trên ngọn đồi đón gió, kể về Q và C hai người bạn thanh mai trúc mã của nhau.
Họ đã cùng nhau trải qua nhiều kỷ niệm đẹp trên ngọn đồi của mình, khiến cho C không thể quên được. Rồi đến một ngày C quyết định nỗ lực để chiếm được trái tim của Q. Nhưng Q là một cô nàng nghịch ngợm và lắm trò nên chàng C của chúng ta cũng chẳng thể chinh phục một cách dễ dàng.

Q cho C một thử thách là cõng Q đi qua hết cả ~N~ ngọn đồi đón gió. Các ngọn đồi này được nối với nhau bởi M con đường mòn một chiều (giữa hai ngọn đồi chỉ có không quá một con đường như thế), mỗi con đường nối giữa hai ngọn đồi ~u,v~ thì để đi qua, cần có yêu cầu về thể lực riêng là ~w~. Do đó, yêu cầu về thể lực của C khi đi qua một chặng gồm nhiều con đường mòn sẽ là max các giá trị ~w~ trên mỗi con đường mòn riêng. Nói một cách ngắn gọn, Q muốn được C cõng đi thăm hết cả ~N~ ngọn đồi này trên những con đường mòn thơ mộng, một ngọn đồi có thể qua bao nhiêu lần tùy thích nhưng quan trọng là phải đi đủ hết; đồng thời, xuất phát ở đâu thì phải kết thúc ở đó. Đây là một thử thách rất lớn cho C, vì rõ ràng có thể có khả năng không đi được, hoặc là đòi hỏi về thể lực lại quá cao.

Cảm động cho điều này, một thiên sứ tình yêu đã cho C một khả năng rất hay là: có thể chọn ra vài con đường mòn và đổi chiều của chúng (ban đầu đi từ ~u \to v~ thì lúc sau sẽ thành đi từ ~v \to u~), nhưng vẫn giữ nguyên giá trị ~w.~ Mỗi con đường chỉ được chọn và đổi không quá một lần và tất nhiên C có thể cũng không cần đổi lần nào. Với phép màu đó, bạn hãy tính thử xem yêu cầu về thể lực nhỏ nhất mà C cần có là bao nhiêu, để C biết mà còn luyện tập cho đạt. Tất nhiên, đôi khi phép màu cũng không giúp ích được, nghĩa là cho dù có đổi chiều thế nào thì cũng không qua được hết ~N~ ngọn đồi, điều này có thể khiến C trầm cảm một thời gian.

Input

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

• Trong ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u, v, w~ với ~1 \le u, v \le N~ và ~1 \le w \le 10^9~, mô tả con đường thứ ~i~ từ ~u~ đến ~v~ cũng như đòi hỏi về thể lực ~w~ trên con đường đó.

Output

Nếu không có cách nào đổi chiều mà đi được qua hết ~N~ ngọn đồi thì in ra ~-1~. Nếu có cách đi được và hơn nữa, có thể điều chỉnh hướng của các con đường để cho yêu cầu về thể lực càng nhỏ càng tốt thì in ra giá trị nhỏ nhất đó.

Sample Input 1

3 3
1 2 1
2 3 2
3 1 3

Sample Output 1

3

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

-1

Sample Input 4

5 8
1 2 4
2 3 5
3 4 6
4 5 3
3 5 1
1 3 7
1 4 9
2 5 8

Sample Output 4

7

Giải thích:

• Trong VD1, C có thể cõng Q đi qua các ngọn đồi theo thứ tự ~1 \to 2 \to 3 \to 1~ và thể lực cần thiết là ~3~ (ở đây C không cần đổi chiều con đường nào cả).

• Trong VD2, C lúc đầu không thể đi được nhưng có thể đổi hướng cạnh ~1 \to 3~ thành ~3 \to 1~ thì đi được qua hết các đỉnh với yêu cầu thể lực là ~3~.

• Trong VD3, C có thể theo hướng ~1 \to 2 \to 3 \to 4~ qua được ~4~ ngọn đồi nhưng lại không có cách nào quay về vị trí xuất phát là ~1.~

• Trong VD4, ta có thể đổi hướng đường ~3 \to 5~ thành ~5 \to 3~, đổi ~1 \to 3~ thành ~3 \to 1~ thì sẽ có cách đi là: ~1 \to 2 \to 3 \to 4 \to 5 \to 3 \to 1~, xuất phát từ ~1~ và quay được về ~1~, yêu cầu thể lực chỉ có ~7~, sẽ có những cách đi khác dùng cạnh ~(1,4)~ hay ~(2,5)~ nhưng cần các năng lực lớn hơn không cần thiết.

---

Theo bạn, còn có thử thách nào khó hơn như vậy nữa không?

" " "
Q: Uầyyy bầu trời hôm nay đẹp vậy!!
Q: Này này cậu nhìn những vì sao kia kìa đẹp thật đấy
C: Đúng đúng đúng
Q: Nếu tớ có khả năng nối những vì sao ấy lại thì chuyện gì sẽ xảy ra nhỉ?
" " "

Vấn đề này có thể được gọi là trò chơi nối sao của Q và C. Trong một đêm cả hai cùng ngước nhìn lên thì họ nhìn thấy trước mắt mình là một bầu trời với ~N~ ngôi sao đang tỏa sáng lấp lánh, những ngôi sao này được Q gọi là những ngôi sao cô đơn. Vì vậy, cậu ấy đã tưởng tượng ra một đường thẳng để nối hai ngôi sao ấy lại với nhau. Nhưng cậu ấy lại lo sợ rằng đường thẳng mình vừa vẽ sẽ biến mất và những ngôi sao ấy lại phải cô đơn một lần nữa, Q tự gọi những đường thẳng này là cạnh cầu, cạnh cầu là cạnh mà khi xóa đi sẽ tăng số lượng ngôi sao cô đơn (theo học thuyết của Q). Vì vậy cậu ấy đã quay sang hỏi C là sau khi mà cậu ấy nối hai ngôi sao bất kỳ lại thì sẽ có bao nhiêu cạnh cầu và nếu mà C không trả lời được thì Q sẽ mãi nằm ở đây vẽ vẽ @@. Vì mãi lo ngắm Q nên C không thể nào trả lời được câu hỏi này, bạn hãy giúp cậu ấy nhé.

Input:

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ cho biết số ngôi sao và số câu hỏi của Q dành cho C với ~2 \le N \le 10^5~ và ~1 \le M \le 2 \cdot 10^5.~

• ~M~ dòng tiếp theo bao gồm hai số nguyên ~u~ và ~v~ nghĩa là Q sẽ nối ngôi sao thứ ~u~ và ngôi sao thứ ~v~ lại với nhau, trong đó ~1 \le u, v \le N.~

• Dữ liệu đảm bảo rằng không có hai ngôi sao nối với nhau nhiều hơn ~1~ lần và sẽ không có ngôi sao nào tự nối với chính nó và các ngôi sao này sẽ được Q đánh số từ ~1~ đến ~N~.

Output:

Với mỗi câu hỏi của Q, bạn hãy nói cho C biết số cạnh cầu hiện tại mà cậu ấy đã vẽ.

Sample Input

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

Sample Output

1
2
0
0
1
0
1
2
0

---

Mong ước của tớ là:

Nhìn thấy nụ cười của cậu mỗi sáng...

C có rất nhiều điều mong ước và muốn gửi gắm cho Q. Tuy nhiên, vì không muốn nói thẳng ra nên đôi khi, C mã hóa các mong ước đó lại, viết vào quyển sổ nhật ký. Chẳng hạn từ một mong ước dạng chuỗi ký tự ~s = abcd~, C có thể mã hóa thành ~s_1 = aaabccccccdd~ hoặc ~s_2 = abbbbccd~, ... nói chung là có rất nhiều cách. Tất nhiên việc mã hóa thô sơ này sẽ dẫn đến việc nhiều thông điệp khác nhau khi giải mã ngược lại có thể lại ra cùng một chuỗi (chẳng hạn ~s_1, s_2~ ở trên khi giải mã lại ra được cùng chuỗi ~s~).

Một ngày nọ, Q tình cờ đọc trộm được nhật ký của C và đọc được ~n~ điều mong muốn mà C dành cho Q. Tuy nhiên, vì có quá nhiều mong ước nên Q muốn biết rằng, trong số đó, có thực sự bao nhiêu thông điệp là đôi một khác nhau (trước khi mã hóa), hãy giúp Q tìm ra nhanh chóng điều này nhé.

Input

Dòng đầu gồm số nguyên dương ~n \le 10^5~ là số lượng mong ước đã được mã hóa, mỗi dòng tiếp theo là một chuỗi độ dài không vượt quá ~100.~

Output

Số lượng mong ước khác nhau trong đó.

Sample input 1

4
aaaaabbbbbc
abc 
aaabbbccccccccc
abcccccccc

Sample output 1

1

Sample input 2

4
iiiiillllyyyyy
tyyyyccc
tyc
illlllllllly

Sample output 2

2

Giải thích

Trong VD1, ta thấy tất cả đều xuất phát từ cùng một chuỗi ~abc~, còn trong VD2, ta có hai chuỗi là ~ily~ và ~tyc~.

---

Sau những ngày rong chơi khắp nơi, Q và C đã nhặt được ~N~ mảnh gỗ, trong đó mỗi mảnh đều có dạng hình chữ nhật với chiều dài là ~a~ và chiều rộng là ~b~. Để bớt nhàm chán, Q đã rủ C chơi một trò chơi mà cô đã tự nghĩ ra, cụ thể luật chơi được mô tả như sau:

Hãy gom nhóm các mảnh gỗ thành một hay nhiều nhóm. Trong đó số điểm của mỗi nhóm được tính bằng tích của chiều dài lớn nhất và chiều rộng lớn nhất của các mảnh gỗ. Chẳng hạn nếu bạn gom hai miếng gỗ có kích thước là ~3 \times 5~ và ~2 \times 5~ thành một nhóm thì số điểm của nhóm này sẽ là ~\max\{3,2 \} \times \max \{5,5 \} = 15~. Người chiến thắng của trò chơi là người có thể thu được tổng số điểm nhỏ nhất có thể. Vì đây là trò chơi của Q nên cậu ấy không muốn thua một chút nào, nên hãy giúp cậu ấy chiến thắng trò chơi này nhé (mặc dù kiểu gì thì C cũng sẽ để cho Q thắng :3 ). Cụ thể hơn, bạn hãy giúp cậu ấy in ra tổng số điểm nhỏ nhất có thể của trò chơi. Chú ý rằng: C không được phép xoay miếng gỗ.

Input:

• Dòng đầu tiên gồm một số nguyên ~N~ là số lượng các miếng gỗ với ~1 \le N \le 2 \cdot 10^5.~

• ~N~ dòng tiếp theo mỗi dòng sẽ chứa hai số nguyên là ~a_i~ và ~b_i~ tương ứng là chiều dài và chiều rộng của miếng gỗ thứ ~i~ với ~1 \le a_i, b_i \le 10^6~.

Output:

Tổng điểm nhỏ nhất có thể có.

Sample Input 1

5
15 15
100 1
3 7
1 100
20 5

Sample Output 1

500

Sample Input 2

5
1 5
2 4
3 2
4 3
5 1

Sample Output 2

25

Giải thích

Trong VD1, cách tối ưu để gom nhóm các mảnh gỗ trên là:

• Nhóm đầu tiên là ~100 \times 1 = 100.~

• Nhóm thứ hai là ~1 \times 100 =100.~

• Nhóm thứ ba là ~3 \times 7, \, 20 \times 5, \, 15 \times 15~, ta có chiều dài lớn nhất là ~20,~ chiều rộng lớn nhất là ~15~ nên điểm số sẽ là ~300.~

Suy ra tổng ba nhóm trên ta sẽ được số điểm nhỏ nhất là ~500.~

Còn trong VD2, cách tối ưu là hai mảnh gỗ đầu tiên thành một nhóm với điểm là ~10~, ba mảnh gỗ sau thành một nhóm với điểm là ~15,~ tổng sẽ bằng ~25.~

---

Theo bạn như thế nào được gọi là an nhiên? Là hai đứa trẻ ngày ngày cùng nhau rong chơi qua những ngọn núi, qua những cánh đồng hay là ngày ngày cùng nhau cười đùa chuyện trò hay là cùng nhau chơi những trò mà cả hai cùng nghĩ ra, hmmm tớ cũng không biết nữa...

""""
C: Sau này gặp lại tớ nhất định sẽ tặng cho cậu một bó hoa tulip
Q: Sao lại là hoa tulip?
C: Vì nó tượng trưng cho tình yêu vĩnh cữu.
""""

Bạn có biết không, hoa tulip là một loài hoa đặc biệt với đa dạng màu sắc. Với sự kết hợp của nhiều sắc tố trong cánh hoa, màu sắc của chúng có thể biến đổi dựa trên nhiệt độ và ánh sáng mặt trời. Bên cạnh đó, hoa tulip còn có một hệ thống di truyền phức tạp. Ví dụ như việc lai hoa đỏ với hoa xanh có thể tạo ra hoa màu tím. Số lượng cánh hoa của hoa cha và hoa mẹ cũng có thể ảnh hưởng đến số cánh hoa của hoa con. Ví dụ, nếu hoa mẹ có ~5~ cánh và hoa cha có ~3~ cánh, thì hoa con có thể có ~8~ cánh. Điều này được gọi là "học thuyết Aquarius" :>

Biết được điều này nên Q đã đem một sơ đồ gia phả hoa tulip ra đố C. Thay vì đố về màu sắc, Q quyết định đố C về số lượng cánh hoa của các hoa con (vì biết rằng cậu ấy rất hay rối rem với màu sắc ":3" ). Q cho C tất cả ~N~ bông hoa và được đánh số từ ~1~ tới ~N~ với hoa số ~1~ là cội nguồn của tất cả bông hoa khác. Và một mảng số nguyên ~a~ với ~a_i~ tương ứng là số cánh hoa của bông hoa tulip thứ ~i~. Nhiệm vụ của bạn là trả lời ~t~ câu hỏi của Q với một trong hai kiểu sau:

• Thay đổi số cánh hoa hiện tại của hoa tulip thứ ~x~ thành ~y~.
• Tổng số cánh hoa của các hoa con tạo ra từ hoa tulip thứ ~x~ là bao nhiêu?

Ta được biết rằng sơ đồ gia phả của hoa tulip trên có thể được hiểu theo đồ thị cây có gốc trong lý thuyết đồ thị. Để dễ hiểu hơn, bạn có thể tham khảo link sau: https://en.wikipedia.org/wiki/Tree(graphtheory).

Input:

• Dòng đầu tiên gồm một số nguyên ~N~ và ~Q~ là số lượng bông hoa cùng với số câu hỏi, với ~1 \le N, Q \le 2 \cdot 10^5~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ là số lượng cánh hoa của bông hoa thứ ~i~, trong đó ~1 \le a_i \le 10^9.~

• Tiếp theo là ~N-1~ dòng, mỗi dòng chứa ~2~ số nguyên ~a~ và ~b~ cho biết có cạnh nối giữa hoa ~a~ và ~b.~

• Cuối cùng, có ~Q~ dòng mô tả các câu hỏi của Q ở một trong hai dạng:

• Câu hỏi loại 1 sẽ có dạng: ~1~ ~x~ ~y~ nghĩa là thay đổi số cánh hoa của hoa ~x~ thành ~y~
  
• Câu hỏi loại 2 sẽ có dạng: ~2~ ~x~ trả lời tổng số cánh hoa của các hoa con tạo ra từ hoa tulip thứ ~x.~

Output:

Trả lời tất cả các câu hỏi loại 2 ở từng dòng khác nhau.

Sample Input

7 3
4 2 5 2 3 19 6
1 2
1 3
3 5
3 4
5 6
5 7
2 5
1 5 0
2 5

Sample Output

28
25

---

Nếu như lần sau gặp được cậu
Hy vọng sẽ là một ngày nắng đẹp