Cho một cây bao gồm ~n~ đỉnh và ~n-1~ cạnh. Với mỗi cạnh theo thứ tự đầu vào, tìm số đường đi đơn phân biệt đi qua cạnh đó modulo 67.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~ là số lượng đỉnh của cây.

~n-1~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~u_i~, ~v_i~ là cạnh thứ ~i~ của cây.

Output

In ra ~n-1~ số, số thứ ~i~ là số lượng đường đi đơn phân biệt đi qua cạnh thứ ~i~ của cây theo thứ tự nhập vào modulo 67.

Scoring

Sample Input 1

3
1 2
2 3

Sample Output 1

2 2

Cho hàm số ~f(i)~ được định nghĩa bởi công thức sau: ~\begin{cases} f(0) = 1 \\ f(n) = 1 \times f(n-1) + 2 \times f(n-2) + \dots + n \times f(0) \end{cases}~

Tính giá trị của ~f(n) \bmod 2718281828~ với ~t~ bộ dữ liệu đầu vào.

Input

Dòng đầu tiên gồm số nguyên dương ~t~ ~(t \le 10^5)~ là số lượng câu hỏi.

~t~ dòng tiếp theo, mỗi dòng chứa một số tự nhiên ~n~ ~(0 \le n \le 10^{18})~.

Output

In ra ~t~ dòng, mỗi dòng là giá trị ~f(n) \bmod 2718281828~ tương ứng.

Scoring

Sample Input 1

3
1
2
314159265353897932

Sample Output 1

1
3
848560825

Cho hai xâu ký tự ~S~ và ~T~ cùng độ dài ~n~, chỉ chứa ~c~ chữ cái đầu tiên trong bảng chữ cái tiếng Anh viết thường (từ ký tự thứ 1 đến ký tự thứ ~c~). Một thao tác shift một ký tự là thay đổi ký tự đó thành ký tự kế tiếp trong bộ chữ cái ~c~ ký tự này. Cụ thể, nếu ký tự là ký tự thứ ~i~ ~(1 \le i < c)~, nó sẽ trở thành ký tự thứ ~i+1~. Nếu ký tự là ký tự thứ ~c~, nó sẽ quay trở lại thành ký tự thứ 1 (ví dụ với ~c=3~, ~'a' \rightarrow 'b'~, ~'b' \rightarrow 'c'~, ~'c' \rightarrow 'a'~).

Có 3 loại truy vấn cần thực hiện:

• 1 l r x: Thực hiện thao tác shift các ký tự từ vị trí ~l~ đến ~r~ của xâu ~S~ tổng cộng ~x~ lần.

• 2 l r x: Thực hiện thao tác shift các ký tự từ vị trí ~l~ đến ~r~ của xâu ~T~ tổng cộng ~x~ lần.

• 3 l: So sánh hai hậu tố ~S[l \dots n]~ và ~T[l \dots n]~. In ra ~<~ nếu xâu ~S~ bé hơn, ~>~ nếu xâu ~S~ lớn hơn, hoặc ~=~ nếu hai xâu bằng nhau (theo thứ tự từ điển).

Input

Dòng đầu tiên gồm ba số nguyên dương ~n~, ~c~ và ~q~ ~(1 \le n, q \le 2 \times 10^5, 2 \le c \le 26)~.

Dòng thứ hai chứa xâu ~S~, dòng thứ ba chứa xâu ~T~. Cả hai xâu đều có độ dài ~n~ và chỉ chứa ~c~ ký tự đầu tiên của bảng chữ cái tiếng Anh.

~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng đã mô tả. Trong các truy vấn loại 1 và 2, ~1 \le l \le r \le n~ và ~1 \le x < c~. Với truy vấn loại 3, ~1 \le l \le n~.

Output

Với mỗi truy vấn loại 3, in ra kết quả tương ứng (~<~, ~>~, hoặc ~=~) trên một dòng.

Scoring

Sample Input 1

3 4 3
abc
abd
3 1
1 3 3 1
3 1

Sample Output 1

<
=

Bạn là chủ của tòa chung cư lớn nhất thế giới mang tên "Thành Phố Trên Mây". Tòa chung cư này là một hình chữ nhật gồm ~n~ tầng, mỗi tầng có ~m~ phòng được đánh số từ trái qua phải. Vào một ngày đẹp trời, hệ thống mạch điện của bạn bị lỗi một cách rất nghiêm trọng và bạn ngay lập tức gọi thợ điện.

Sau một hồi mày mò, bạn được biết rằng công tắc của một phòng điều khiển đèn của tất cả các phòng trên cùng tầng và cùng cột với phòng đó. Cụ thể hơn, khi bật công tắc của phòng ~(i, j)~, tức phòng thứ ~j~ của tầng ~i~, tất cả các phòng thuộc tầng ~i~ hoặc cột ~j~ đều bị ảnh hưởng (mỗi phòng bị ảnh hưởng đúng một lần). Khi một phòng bị ảnh hưởng, đèn của phòng đó đổi từ bật (1) thành tắt (0) hoặc tắt (0) thành bật (1).

Tuy nhiên, các thợ điện cần thêm thời gian để chuẩn bị vật liệu để sửa chữa hệ thống điện của tòa chung cư này. Tối hôm đó, cư dân trong tòa nhà bắt đầu than phiền vì đèn liên tục bật tắt bất thường, khiến họ không thể ngủ. Không còn cách nào khác, bạn quyết định tự mình can thiệp vào hệ thống bằng cách sử dụng những công tắc hiện có để tắt hết đèn để cư dân được ngủ.

Input

Dòng đầu tiên chứa số nguyên ~S~ ~(1 \le S \le 5)~ là số thứ tự subtask của test. Dòng tiếp theo chứa số nguyên ~T~ ~(1 \le T \le 10)~ là số lượng trường hợp bạn cần xử lý. Mỗi trường hợp có định dạng như sau:

• Dòng đầu tiên chứa 2 số nguyên ~n, m~ ~(n, m \le 1000)~.

• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số, mỗi số là số 0 hoặc 1. Số thứ ~j~ trên dòng thứ ~i~ là trạng thái đèn của phòng ~(i, j)~ (0 là tắt, 1 là bật).

Dữ liệu đầu vào đảm bảo ~\sum n \times m \le 10^6~ qua các trường hợp.

Output

Với mỗi trường hợp:

• Nếu không có cách để tắt hết đèn, in ra NO.

• Ngược lại, in ra ~n+1~ dòng. Dòng đầu in ra YES và ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số 0 hoặc 1 với số thứ ~j~ trên dòng thứ ~i~ là 1 nếu bạn muốn bật công tắc tại phòng ~(i, j)~ và 0 nếu ngược lại.

Scoring

Sample Input 1

1
2
2 2
1 1
1 0
3 3
1 0 1
0 1 0
1 0 1

Sample Output 1

YES
1 0
0 0
NO

Notes

Trong ví dụ đầu, việc bật công tắc của phòng ~(1, 1)~ sẽ thay đổi trạng thái của các phòng ~(1, 1), (1, 2), (2, 1)~ thành 0 và hoàn thành bài toán.

Trong ví dụ thứ hai, không tồn tại một cách để tắt hết đèn của các phòng.

Cho một dãy gồm ~n~ số nguyên dương ~a_{1}, a_{2}, ..., a_{n}~. Có ~q~ truy vấn, mỗi truy vấn cung cấp một số nguyên dương ~v~.

Với mỗi truy vấn, hãy đếm xem có bao nhiêu số ~a_{i}~ trong dãy chia hết cho ~v~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n, q \le 2 \times 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, ..., a_{n}~ ~(0 < a_{i} \le 10^6)~.

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~v~ ~(1 \le v \le 10^9)~.

Output

In ra ~q~ dòng, mỗi dòng chứa một số nguyên là số lượng số ~a_{i}~ chia hết cho ~v~ tương ứng với truy vấn đó.

Scoring

Sample Input 1

5 3
1 4 5 7 10
2
4
3

Sample Output 1

2
1
0

Cho một mảng ~a~ gồm ~n~ số nguyên dương ~(0 < a_{i} < 10^9)~.

Định nghĩa giá trị của một mảng là số nguyên thu được bằng cách viết liền các phần tử của mảng đó theo thứ tự từ trái sang phải.

Ví dụ, nếu mảng là ~[12, 3, 45]~, giá trị của mảng sẽ là ~12345~.

Yêu cầu: Hãy tính tổng giá trị của tất cả các hoán vị của mảng ~a~. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9+7~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(n \le 200)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, ..., a_{n}~ ~(a_{i} < 10^9)~.

Output

In ra một số nguyên duy nhất là tổng giá trị của mọi hoán vị lấy dư cho ~10^9+7~.

Scoring

Sample Input 1

2
12 3

Sample Output 1

435

Notes

Trong ví dụ trên, có ~2~ hoán vị:

• ~[12, 3] \rightarrow 123~

• ~[3, 12] \rightarrow 312~

Cho ~n~ điểm phân biệt trên mặt phẳng tọa độ ~Oxy~.

Một parabol có phương trình dạng ~y = x^2 + ax + b~ được gọi là thỏa mãn nếu nó đi qua ít nhất ~2~ điểm trong số ~n~ điểm đã cho và không có điểm nào trong số ~n~ điểm nằm phía trên parabol đó.

Yêu cầu: Hãy đếm số lượng parabol thỏa mãn khác nhau.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(2 \le n \le 10^5)~.

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_{i}, y_{i}~ mô tả tọa độ của điểm thứ ~i~ ~(|x_{i}|, |y_{i}| \le 10^6)~. Các điểm được cho là đôi một phân biệt.

Output

In ra một số nguyên duy nhất là số lượng parabol thỏa mãn tìm được.

Scoring

Sample Input 1

3
0 0
1 1
2 4

Sample Output 1

1

Notes

Một điểm ~(x_{i}, y_{i})~ được gọi là nằm phía trên parabol ~y = x^2 + ax + b~ nếu ~y_{i} > x_{i}^2 + ax_{i} + b~.

Trong ví dụ trên, parabol ~y = x^2~ (với ~a = 0~, ~b = 0~) đi qua cả ~3~ điểm và không có điểm nào nằm phía trên nó.

Cho một cây gồm ~n~ đỉnh. Với một tập hợp các đỉnh ~A \subseteq \{1, 2, ..., n\}~, gọi ~g(A)~ là giá trị ~k~ nhỏ nhất sao cho tồn tại ~k~ đường đi trên cây thỏa mãn các điều kiện sau:

• Mỗi đường đi không đi qua bất kỳ cạnh nào quá một lần (đường đi đơn).

• Mỗi đỉnh thuộc tập ~A~ đều được đi qua bởi ít nhất một đường đi trong tập ~k~ đường đi đó.

Ban đầu, ta có một tập hợp ~S~ rỗng. Có ~q~ truy vấn, mỗi truy vấn bao gồm một đỉnh ~u~.

• Nếu ~u \in S~, thực hiện xóa ~u~ khỏi tập ~S~.

• Nếu ~u \notin S~, thực hiện thêm ~u~ vào tập ~S~.

Yêu cầu: Sau mỗi truy vấn, hãy in ra giá trị ~g(S)~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n, q \le 3 \times 10^5)~.

• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một cạnh của cây.

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~u~ mô tả đỉnh được thay đổi trong tập ~S~.

Output

In ra ~q~ dòng, mỗi dòng là giá trị ~g(S)~ sau khi thực hiện truy vấn tương ứng.

Scoring

Sample Input 1

3 2
1 2
2 3
1
3

Sample Output 1

1
1