Để tiết kiệm bộ nhớ khi lưu trữ, người ta thường sử dụng các thuật toán nén trước khi lưu và tiến hành giải nén trước khi sử dụng. Đối với văn bản, có một thuật toán gọi là "Run-Length Encoding".

• Ví dụ xâu "aaabcccc" sẽ được mã hoá thành "a3b1c4"

Xem hình dưới đây để hiểu rõ hơn về thuật toán này:

Hiếu mới được mẹ mua cho 1 con Macbook Pro M2 có dung lượng 1TB SSD. Tuy nhiên, cậu cảm thấy việc lưu tài liệu mà không nén sẽ có thể sẽ khiến máy tính phải tiêu thụ nhiều năng lượng hơn. Do đó, bạn hãy giúp Hiếu viết 1 chương trình cho phép nén các chuỗi của bạn ấy theo thuật toán "Run-Length Encoding" nhé.

Input

• Dòng đầu tiên là số nguyên ~T~, là Số lượng chuỗi Hiếu cần bạn giúp
• T dòng tiếp theo, mỗi dòng là một chuỗi ký tự ~S~

Output

• In ra ~T~ dòng, mỗi dòng là chuỗi đã mã hoá tương ứng.

Sample

Input #1

2
a
aaabcccc

Output #1

a1
a3b1c4

Giới hạn

• ~0 < T \le 20~
• Các chuỗi cần mã hoá ~S~ có độ dài không quá ~1000~ và chỉ bao gồm các chữ cái ~a-z~ trong bảng chữ cái tiếng Anh.

Cho một đường thẳng đi qua hai điểm ~A(x_A, y_A)~, ~B(x_B, y_B)~, và một điểm ~C(x_C, y_C)~ tự do.

Hãy cho biết điểm ~C~ nằm trên, bên trái hay bên phải đường thẳng ~AB~. Biết rằng vị trí này được xác định bằng cách đứng tại điểm ~A~ và nhìn về hướng tới điểm ~B~.

Input

• Gồm 3 dòng, mỗi dòng gồm 2 số nguyên lần lượt là toạ độ ~x~ và ~y~ của 3 điểm ~A~, ~B~, ~C~.

• ~(-10^9 \leq x_{A,B,C} , y_{A,B,C} \leq 10^9)~.

• Input sẽ có dạng:

xA yA
xB yB
xC yC

Output

• Gồm 1 dòng gồm 1 số nguyên mô tả tương quan vị trí của điểm ~C~ so với đoạn thẳng ~AB~.
• Nếu nằm bên trái, in ra ~-1~.
• Nều nằm bên phải, in ra ~1~.
• Nếu nằm trên đường thẳng chứa ~AB~, in ra ~0~.

Sample

Input #1

1 1
5 3
2 3

Output #1

-1

Input #2

0 2
10 1
-1 2

Output #2

1

Input #3

1 1
5 3
3 2

Output #3

0

YugiHacker có một dãy số nguyên dương ~N~ phần tử và ~Q~ truy vấn, mỗi truy vấn YugiHacker sẽ chọn ra một phần tử và nhân nó lên một lượng là ~x~, hãy tính Bội chung nhỏ nhất của dãy sau khi thực hiện mỗi truy vấn này.

Vì kết quả có thể rất lớn, bạn hãy in ra kết quả sau khi chia phần dư ~10^9 + 7~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, Q~ ~(1 \leq N, Q \leq 10^5)~.
• Dòng tiếp theo là ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq 10^5)~.

• ~Q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~i~, ~x~ ~(1 \le i \le n, 1 \le x \le 10^5)~.

• Input sẽ có dạng:

N Q
a1 a2 a3 ... aN
i1 x1
i2 x2
...
iQ xQ

Output

• Với mỗi truy vấn in ra kết quả trên 1 dòng.

Sample

Input #1

5 3
1 2 3 4 5
2 2
1 7
5 18

Output #1

60
420
1260

Trang đang trong thời gian nghỉ hè nên cô ấy quyết định dậy sớm từ 6h để tập thể dục giảm cân.

Khu Trang sống có ~N~ thành phố và có ~N-1~ con đường. Sáng sớm Trang sẽ chạy xung quanh khu phố này để tập thể dục.
Hãy tính độ dài đường đi xa nhất giữa ~2~ khu phố mà Trang có thể đi được. Biết rằng từ 1 thành phố có thể đi đến tất cả các thành phố còn lại.

Độ dài đường đi giữa 2 khu phố được tính bằng số con đường đi đi qua trên quãng đường đó.

Input

• Dòng đầu tiên gồm 1 số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~.

• ~N-1~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u~, ~v~ mô tả đường đi giữa 2 thành phố ~u~ và ~v~ ~(1 \leq u, v \leq N)~.

• Input sẽ có dạng:

N
u1 v1
u2 v2
...
uN vN

Output

• Gồm 1 dòng chứa 1 số nguyên là độ dài đường đi xa nhất giữa ~2~ khu phố mà Trang có thể đi được.

Sample

Input #1

5
1 2
2 3
2 4
1 5

Output #1

3

Giải thích #1

• Đường đi dài nhất sẽ là ~5 \rightarrow 1 \rightarrow 2 \rightarrow 3~ hoặc ~5 \rightarrow 1 \rightarrow 2 \rightarrow 4~. Vậy độ dài đường đi xa nhất sẽ là ~3~.