Dãy chính phương là dãy số nguyên dương có tổng các số trong dãy đó tạo thành một số chính phương. Có thể có nhiều dãy chính phương với cùng độ dài.

Cho số nguyên dương ~n~, hãy tìm một dãy chính phương với ~n~ phần tử phân biệt. Nếu có nhiều dãy như vậy, hãy đưa ra một dãy bất kì với giá trị các phần tử không vượt quá ~10^9~.

Input

• Một số nguyên dương ~n~ (~n\le 1000~)

Output

• In ra ~n~ số nguyên mô tả dãy chính phương bạn tìm được.

Scoring

• Subtask ~1~ (~25~ điểm): ~n\le 10~

• Subtask ~2~ (~75~ điểm): Không có điều kiện gì thêm

Sample Input 1

3

Sample Output 1

5 4 7

Trong chuyến tham quan của mình, Lyn dừng chân tại một khách sạn huyền bí và quyết định sẽ ngủ lại một đêm tại đây. Người quản lí khách sạn thông báo rằng hiện tại một số phòng của khách sạn đã được thuê, chỉ còn lại các phòng với số phòng là một số nguyên nằm trong đoạn từ ~L~ đến ~R~ là còn trống.

Vì có một sự yêu thích đặc biệt với số đối xứng nên trong các chuyến tham quan của mình Lyn sẽ chỉ ở phòng khách sạn mà số phòng là một số đối xứng. Hứng thú trước sở thích đặc biết của Lyn, người quản lý khách sạn hứa sẽ miễn phí tiền phòng nếu cô có thể tính được tổng giá trị số phòng của các phòng còn trống mà thỏa mãn sở thích của cô. Bạn hãy giúp Lyn trả lời câu đố này nhé.

Biết rằng, số đối xứng là số đọc từ trái qua phải cũng giống như đọc từ phải qua trái. Ví dụ số ~1221,\ 5,\ 131~ là các số đối xứng, còn ~97,\ 345~ thì không.

Input

Một dòng duy nhất gồm hai số nguyên ~L,\ R~ ~(1 \le L \le R \le 10^{9})~.

Output

In ra một số nguyên duy nhất là số phòng còn trống có thể đáp ứng được sở thích của Lyn.

Scoring

• Subtask ~1~ (~40~ điểm): ~1 \le L \le R \le 10^6~.

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

Sample Input 1

5 11

Sample Output 1

46

Notes

Các phòng còn trống thỏa mãn được sở thích của Lyn có số phòng là ~5~, ~6~, ~7~, ~8~, ~9~, ~11~.

Vì vậy đáp là cho câu đố là ~5 + 6 + 7 + 8 + 9 + 11 = 46~

Cho dãy gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~. Bạn có quyền thay đổi các phần tử của dãy số này sao cho ~\forall i~ ~(1 \le i < n)~ ~LCM(a_i, a_{i+1})~ là các số chính phương.

Tại mỗi bước thay đổi, bạn chọn một vị trí ~i~ bất kì (~1 \leq i \leq n~) và cập nhật ~a_i~ := ~a_i \times x~ với ~x~ là một số nguyên dương bất kì. Không giới hạn số lần thay đổi của một phần tử.

Hãy tính số lần thay đổi tối thiểu để thỏa mãn yêu cầu đề bài.

Input

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

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

• Gồm một số nguyên không âm duy nhất là kết quả của đề bài.

Scoring

• Subtask ~1~ (~30~ điểm): ~n \le 1000~, ~a_i \le 5~ ~\forall~ ~1 \le i \le n~.

• Subtask ~2~ (~70~ điểm): Không có điều kiện gì thêm.

Sample Input 1

4
6 4 2 3

Sample Output 1

2

Sample Input 2

4
4 1 2 3

Sample Output 2

1

Notes

Ta có thể thay đổi dãy thành ~[162, 4, 2, 36]~ sau khi thay đổi phần tử đầu tiên và phần tử cuối cùng.

Trong thiết kế hệ thống, kiểm thử là một giai đoạn vô cùng quan trọng. ~\textbf{Quân}~ đang thiết kế một máy theo nguyên lí máy Turing, tức là thực hiện các thao tác trên một băng ghi bộ nhớ; và máy của anh đang trong giai đoạn kiểm thử.

Băng ghi bộ nhớ của ~\textbf{Quân}~ có thể coi là một dãy ~n~ bit được đánh số từ ~1~ đến ~n~. Từ trái sang phải, mỗi bit ban đầu có một trạng thái xác định. Để kiểm tra máy, người ta lần lượt thực hiện các truy vấn thuộc trong hai loại:

+ ~1~ ~l~ ~r~: Chuyển trạng thái các bit từ bit thứ ~l~ đến bit thứ ~r~ (~0~ thành ~1~ và ~1~ thành ~0~).

+ ~2~ ~x~ ~y~ ~z~ ~t~: Kiểm tra xem hai dãy nhị phân con từ ~x~ đến ~y~ và từ ~z~ đến ~t~ có giống nhau không?

Yêu cầu: Bạn hãy giúp ~\textbf{Quân}~ kiểm tra máy của anh bằng cách trả lời các truy vấn loại ~2~ nhé!

Input

Dòng đầu tiên chứa xâu nhị phân ~S~ ~(|S| \le 10^{5})~ mô tả trạng thái băng nhớ ban đầu.

Dòng thứ hai chứa số nguyên dương ~q~ ~( 1 \le q \le 10^{5})~ là số truy vấn.

~q~ dòng tiếp theo mỗi dòng thuộc một trong hai dạng:

• ~1~ ~l~ ~r~ : ~(1 \le l \le r \le |S|)~ .

• ~2~ ~x~ ~y~ ~z~ ~t~ :~(1 \le x \le y \le |S| ,1 \le z \le t \le |S|)~

Output

• In ra nhiều dòng theo thứ tự là đáp án của truy vấn loại ~\textbf{2}~ tương ứng:

• Nếu hai dãy là giống nhau, in ra "YES", ngược lại in ra "NO".

Scoring

• Subtask ~1~ (~15~ điểm): ~1 \le |S| , q \le 1000~.

• Subtask ~2~ (~25~ điểm): Các truy vấn loại ~1~ xảy ra trước loại ~2~.

• Subtask ~3~ (~60~ điểm): Không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

YES
NO
NO

Notes

• Sau truy vấn thứ nhất, xâu ~S~ trở thành ~01011011~.

• Trong truy vấn thứ hai, dãy con từ ~2~ đến ~3~ bằng ~10~, dãy con từ ~5~ đến ~6~ bằng ~10~.

• Sau truy vấn thứ ba, xâu ~S~ trở thành ~10100100~

• Trong truy vấn thứ tư, dãy con từ ~1~ đến ~5~ bằng ~10100~, dãy con từ ~2~ đến ~7~ bằng ~0100100~.

Trong tiết học môn Nhập môn Công nghệ Thông tin, bạn ~H~ đã được học về các phép toán trên bit (bitwise operations). Rất hứng thú với các phép toán này, bạn ~H~ đã định nghĩa một cặp số đáng yêu như sau:

Một cặp số đáng yêu là một cặp 2 số ~a~ và ~b~ khác nhau sao cho:

$$(a \oplus b) \equiv (a \land b) \mod k$$

Với:

• ~\oplus~ là phép toán XOR.

• ~\land~ là phép toán AND.

Bạn ~H~ đi khoe với mọi người về cặp số đáng yêu của mình và sau đó đố ~U~ xem là có bao nhiêu cặp số đáng yêu ~(a, b)~ sao cho ~L \le a < b \le R~. Bạn hãy giúp ~U~ tìm ra đáp án nhé!

Input

Gồm một dòng duy nhất chứa 3 số nguyên dương lần lượt là ~l~, ~r~ và ~k~ (~1 \le l \le r \le 10^{18};\ k \le 10^4~).

Output

Gồm một dòng duy nhất chứa 1 số nguyên không âm duy nhất là số lượng cặp số đáng yêu cần tìm đem chia dư với ~10^9+7~.

Scoring

• Subtask ~1~ (~30~ điểm): ~r-l \le 1000~.

• Subtask ~2~ (~30~ điểm): ~l=1~.

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

Sample Input 1

1 10 3

Sample Output 1

15

Notes

Trong test ví dụ thứ nhất, dưới đây là 15 cặp số đáng yêu thỏa mãn:

Bạn được cho một cây ~n~ đỉnh, số nguyên dương ~k~ và ~m~ đường đi trên cây, đường đi thứ ~i~ nối giữa hai đỉnh ~a_i~ và ~b_i~.

Đếm số cách chọn ra tập ~k~ đường đi ~i_1, i_2, ..., i_k~ (~1 \leq i_1 < i_2 < ... < i_k \leq m~) sao cho với mọi cặp hai đường đi ~i_p~ và ~i_q~ (~1 \leq p < q \leq k~), hai đường đi này giao nhau. Hai đường đi giao nhau nếu tồn tại ít nhất một đỉnh ~w~ (~1 \leq w \leq n~) mà đỉnh ~w~ thuộc cả hai đường đi.

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

Input

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

• ~n - 1~ dòng tiếp theo gồm ~2~ số nguyên dương ~u, v~ là các cạnh của cây

• ~m~ dòng tiếp theo gồm ~2~ số nguyên ~a, b~ là đường đi từ ~a~ đến ~b~ trên cây

Output

In ra một dòng duy nhất là đáp án của bài toán

Scoring

• Subtask ~1~ (~20~ điểm): ~n,m \leq 20~.

• Subtask ~2~ (~20~ điểm): mỗi đỉnh chỉ có tối đa 2 cạnh kề.

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

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

Notes

Trong ví dụ thứ nhất, các tập thỏa mãn là {(~1, 4~), (~1, 5~)}, {(~3, 5~), (~1, 5~)}