Số chín ước là số có chính xác ~9~ ước nguyên dương. Ví dụ:

• Số ~36~ là một số chín ước vì ~36~ có ~9~ ước nguyên dương là ~1, 2, 3, 4, 6, 9, 12, 18~ và ~36~.
• Số ~2006~ không phải là một số chín ước do ~2006~ chỉ có ~8~ ước nguyên dương là ~1, 2, 17, 34, 59, 118, 1003~ và ~2006~.

QioCass đang rất tò mò về số chín ước và muốn biết một số ~n~ có phải là số chín ước không? Các bạn hãy giúp QioCass trả lời câu hỏi nhé.

Input

• Dòng đầu tiên gồm một số nguyên ~T (1 \le T \le 10)~ ~-~ Thể hiện số lượng số cần trả lời.

• Dòng thứ hai gồm ~T~ số nguyên ~X_i (1 \le X_i \le 10^{18})~ ~-~ Thể hiện số thứ ~i~ cần trả lời.

Output

• Gồm ~T~ dòng, in ra YES nếu ~X_i~ là số chín ước, ngược lại in ra NO.

Scoring

Sample Input 1

6
36 256 144 10 6 2006

Sample Output 1

YES
YES
NO
NO
NO
NO

Xâu đơn là xâu gồm ~1~ chữ cái, với độ dài bằng vị trí của chữ cái đó trong bảng chữ cái. Ví dụ:

• a, bb, dddd là những xâu đơn hợp lệ.

• ab, aa, bbbb không phải là xâu đơn.

Xâu ghép là xâu gồm nhiều xâu đơn được ghép lại với nhau, và xâu đơn trước phải có chữ cái bé hơn chữ cái của xâu đơn ở sau, ví dụ:

• a, abb, adddd là những xâu ghép hợp lệ.

• bba, aabb, bbbb không phải là xâu ghép.

Cho xâu ~s~ gồm các chữ cái viết thường, tìm xâu con dài nhất (không nhất thiết phải liên tiếp) trong ~s~ là một xâu ghép. In ra độ dài của xâu đó.

Input

Một dòng duy nhất là xâu ~s~ ~(|s| \leq 10^5)~.

Output

In ra độ dài xâu con dài nhất thõa mãn đề bài.

Scoring

Sample Input 1

adddebbaacccd

Sample Output 1

6

Sample Input 2

abbcdccddd

Sample Output 2

7

Notes

Ở ví dụ ~1~: Xâu ghép dài nhất trong test ví dụ là abbccc.

Ở ví dụ ~2~: Xâu ghép dài nhất trong test ví dụ là abbdddd.

Cho một dãy số nguyên dương ~a~ gồm ~n~ phần tử. Hãy tìm bộ số ~(x,y,z,t)~ (đôi một phân biệt) bất kỳ thỏa mãn ~a_x + a_y = a_z + a_t~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~4 \leq n \leq 2 \cdot 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 2 \cdot 10^6~).

Output

• In ra bộ số bất kì thỏa mãn bài toán.

• Nếu không tồn tại bộ số nào như vậy, in ra ~-1~.

Scoring

Sample Input 1

9
21 13 4 30 30 28 18 5 17

Sample Output 1

1 2 3 4

Sample Input 2

8
25 22 6 24 9 26 25 14

Sample Output 2

1 3 2 5

Vào khoảng thời gian nào đó năm nào đó, thời gian này đang hoành hành rất nhiều Ma sói. Tại một ngôi làng nhỏ ven sông gồm ~n~ người, nơi đây vốn bình yên và nhẹ nhàng trôi qua từng ngày, Bỗng một ngày nọ, Ma Sói xuất hiện làm đảo lộn cuộc sống của mọi người ở đây. Loài động vật này vô cùng khôn khéo, ban ngày thì chúng ở ngụy trang thành dân thường, còn đêm thì chúng trở về thân phận thật của mình và cắn con người. Chính vì vậy, cuộc sống của người dân tại ngôi làng ngày càng trở nên căng thẳng bởi sự nguy hiểm, sự sợ hãi. Không thể sống mãi trong lo sợ và căng thẳng như thế mãi, dân làng quyết định cùng nhau hợp sức lại để chống lại lũ Ma Sói kia. Nhưng cũng thật may mắn, trong làng cũng có một số người dân có năng lực đặc biệt giúp việc tìm ra Ma Sói phần nào bớt khó khăn hơn…

Dù hoảng sợ là thế, nhưng một số người dân trong đây lại thèm trà sữa!? Vì thế, bạn đến từ khu xóm "Tà tưa" mỗi ngày đều phải đi ship trà sữa cho người dân trong làng. Với năng lực đặc biệt của những người dân trong làng, trên bảng tin vào mỗi ngày đều cập nhật thêm một thông tin nào đó về sói như: "Trường là sói cô độc.", "Quang và Trường đều cùng một phe", "Quang và Trường có thể đều là sói, nhưng không có vụ Quang và Trường đều cùng là người", ~\ldots~.

Tuy nhiên với sự thông minh trời phú của mình, bạn nhận ra được điểm khác thường nếu xâu chuỗi tất cả thông tin đã nghe. Có tổng cộng ~q~ ngày, liệu bạn có thể tìm được điểm khác thường dựa vào các thông tin trên bảng tin hay không? Nếu có, hãy xác định thời điểm đầu tiên mà bạn tìm ra được điểm bất thường nhé.

Input

Dòng đầu tiên gồm một số nguyên ~t~ (~1 \le t \le 10^4~) — số lượng bộ test. Với mỗi bộ test:

Dòng đầu tiên của mỗi test gồm hai số nguyên ~n, q~ (~1 \le n \le 10^9~, ~1 \le q \le 10^5~) — số lượng người/sói trong làng và số lượng ngày.

Trong ~q~ dòng tiếp theo của test, mỗi dòng thuộc ~1~ trong ~3~ dạng sau:

• 1 x k: Thông tin cho biết ~x~ ~(1 \le x \le n)~ sẽ là người nếu ~k = 0~ và là sói nếu ~k = 1~.

• 2 x y k: Thông tin cho biết ~x~ ~(1 \le x \le n)~ cùng phe với ~y(1 \le y \le n)~ nếu ~k = 0~ và khác phe nếu ~k = 1~.

• 3 x u y v: Gồm hai mảnh thông tin dạng 1 x u và 1 y v. Thông tin cho biết có ít nhất một mảnh thông tin là sự thật.

Đảm bảo rằng tổng ~q~ của tất cả truy vấn không vượt quá ~10^5~.

Output

Gồm ~t~ dòng, mỗi dòng in thời điểm đầu tiên mà bạn tìm ra được điểm bất thường trong các thông tin đã nghe được. Còn nếu sau cả ~q~ ngày bạn vẫn không tìm ra được điểm bất thường thì in ra ~-1~.

Scoring

Sample Input 1

1
10062006 5
1 1 1
2 1 2 0
1 3 1
1 2 0
3 1 1 3 0

Sample Output 1

4

Notes

Bạn suy luận như sau:

• Thông tin ~1~: cư dân ~1~ là sói;

• Thông tin ~2~: cư dân ~2~ cùng phe cư dân ~1~, cư dân ~2~ là sói;

• Thông tin ~3~: cư dân ~3~ là sói;

• Thông tin ~4~: cư dân ~2~ là người, mâu thuẫn với thông tin ~2~.

Vậy thời điểm đầu tiên xuất hiện điểm bất thường là ~4~.

Ở thành phố Trê, bạn là hướng dẫn viên du lịch. Thành phố của bạn nổi tiếng với ~n~ điểm du lịch và mọi địa điểm đều đi đến các địa điểm khác bằng các con đường trong thành phố. Điều đặc biệt là chỉ có đúng ~n - 1~ con đường dùng để nối các địa điểm lại với nhau. Để đi vào một địa điểm du lịch, đoàn của bạn phải đang đứng ở địa điểm mà địa điểm đi tới phải được nối với điểm du lịch hiện tại.

Nhiệm vụ của bạn là soạn ra các hành trình cho các đoàn du khách tới thành phố của bạn. Mọi địa điểm được đánh số từ ~1~ tới ~n~. Để đơn giản hóa công việc, bạn quyết định diễn đạt nó bằng một dãy số là thứ tự thăm lần đầu tiên của các địa điểm du lịch. Có nghĩa là trên dãy số, địa điểm ~X~ nằm trước địa điểm ~Y~ trên dãy số khi địa điểm ~X~ được ghé thăm lần đầu tiên trước khi địa điểm ~Y~ được ghé thăm lần đầu tiên. Hành trình của bạn sẽ bắt đầu từ một địa điểm và kết thúc khi tất cả mọi địa điểm đã được ghé thăm.

Với bản đồ của thành phố Trê trong tay, bạn quyết định tính xem có bao nhiêu hành trình khác nhau bạn có thể soạn ra khi bắt đầu từ địa điểm ~i~ trong thành phố. Hai hành trình được xem là khác nhau khi hai dãy số tượng trưng cho hành trình là khác nhau.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \le n \le 10^6~) là số lượng điểm du lịch.

~n - 1~ dòng tiếp theo chứa hai số nguyên dương ~a~ và ~b~ (~1 \le a, b \le n~) cho biết có con đường nối địa điểm ~a~ với địa điểm ~b~.

Output

Kết quả được in theo modulo ~10^9 + 7~ trên ~n~ dòng, dòng thứ ~i~ là số lượng hành trình khác nhau khi bắt đầu từ thành phố ~i~.

Scoring

Sample Input 1

5
1 2
2 3
3 4
1 5

Sample Output 1

4
6
4
1
1

Sample Input 2

6
3 6
1 3
4 2
1 4
4 5

Sample Output 2

20
4
10
20
4
2

Notes

Giải thích bộ test đầu tiên:

• Với gốc là ~1~, ta được các hành trình tương ứng là ~(1, 2, 3, 4, 5)~, ~(1, 2, 3, 5, 4)~, ~(1, 2, 5, 3, 4)~, ~(1, 5, 2, 3, 4)~.

• Với gốc là ~2~, ta được các hành trình tương ứng là ~(2, 1, 3, 4, 5)~, ~(2, 1, 3, 5, 4)~, ~(2, 1, 5, 3, 4)~, ~(2, 3, 1, 4, 5)~, ~(2, 3, 1, 5, 4)~, ~(2, 3, 4, 1, 5)~.

• ~\dots~

Ở thành phố Miêu Ti, những con người ở đây đều rất mê trà sữa giống xóm "Tà tưa" vậy!!. Để đáp ứng nhu cầu của những con nghiện tà tưa ở đây, có ~n~ điểm buôn để bán trà sữa. Các điểm buôn có thể tới nhau qua một hoặc các con đường trung gian, tuy nhiên giữa ~2~ điểm buôn bất kì duy chỉ có đúng một cách đi tới nhau.

Bạn là kế toán của một công ty sản xuất nguyên liệu trà sữa và nhiệm vụ của bạn là bán ra được những nguyên liệu ấy tới các điểm buôn với một giá tiền nào đó để có thể thu được tiền bán với giá trị lớn nhất. Ở mỗi điểm buôn ~i~, có ra giá trần ~c_i~ để mua nguyên liệu từ bạn, bạn sẽ có thể bán cho điểm buôn ~i~ nếu mức giá của nguyên liệu bạn bán không được quá ~c_i~.

Bạn sẽ thực hiện nhiệm vụ ấy trong ~q~ ngày. Ở ngày thứ ~t~, bạn sẽ thực hiện một chuyến đi qua các điểm buôn, và bán nguyên liệu cho các điểm buôn mà bạn đã đi qua. Chuyến đi là một đường đi đơn, có nghĩa là mỗi điểm buôn đã đi qua thì không được đi lại. Và không phải bạn muốn đi từ điểm buôn nào hay kết thúc ở đâu cũng được, bạn chỉ có thể bắt đầu đi hay kết thúc chuyến đi tại một trong các điểm buôn thuộc ~s_t~.

Do chuyến đi là xuyên suốt vì thế bạn cần xác định trước số lượng nguyên liệu cũng như mức tiền bán nguyên liệu ấy. Và cũng bởi vì là một người trung thực nên mức giá ấy là không đổi ở tất cả các điểm buôn. Ở các điểm buôn mà bạn đã đi qua, trách việc mất khách tại các điểm ấy bạn cũng cần tính toán giá bán sao cho bạn có thể bán tại tất cả những điểm ấy.

Vì tại mỗi điểm buôn đều mua chính xác ~1~ lần nguyên liệu mà bạn bán ra nên có thể nói nếu bạn đi qua ~x~ điểm buôn thì bạn sẽ bán được ~x~ nguyên liệu với một giá tiền ~k~ nào đó. Ở mỗi ngày như vậy, bạn cần đưa ra tổng số tiền bạn kiếm được hay chính là ~x \cdot k~.

Input

Dữ liệu vào bao gồm:

• Dòng đầu tiên gồm ~3~ số nguyên ~n,m,q~ — Số lượng điểm buôn, số lượng con đường và số ngày cần giải quyết. (~1 \leq n,m,q \leq 2 \cdot 10^5~)

• Dòng thứ ~2~ gồm ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ — Mức giá sàn để mua sản phẩm của các điểm buôn. (~0 \leq c_i \leq 10^9 ∀i 1 \leq i \leq n~).

• Dòng thứ ~j~ trong số ~m~ dòng tiếp theo gồm ~2~ số nguyên ~u_j, v_j~ — Cho biết có đường đi nối trực tiếp giữa ~2~ điểm buôn ~u_j~ và ~v_j~. (~1 \leq u_j, v_j \leq n~ ~∀j~ ~1 \leq j \leq m~).

• Dòng thứ ~t~ trong số ~Q~ dòng cuối cùng gồm số đầu tiên là ~|s_t|~ theo sau là ~|s_t|~ số nguyên — Cho biết tập hợp các điểm buôn có thể bắt đầu, và kết thúc trong chuyến hành trình tại ngày ~t~. (~x ∈ s_i, 1 \leq x \leq n, \sum ^Q _{t=1} |S_t| \leq 2 \cdot 10^5~).

Output

Gồm ~q~ dòng, in ra đáp án của bài toán trên ~1~ dòng.

Scoring

Sample Input 1

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

Sample Output 1

6
3
9