Một tập hợp được coi là phản nhị phân khi tập hợp đó không có đồng thời 2 số dưới dạng ~m~ và ~2*m~.

Ví dụ, tập hợp ~A = {2, 3, 5, 8, 11, 13}~ là tập hợp phản nhị phân, tập hợp ~B = {2, 3, 5, 6, 8, 11, 13}~ không phải, do nó chứa 2 số ~3~ và ~6~.

Công việc của bạn: tìm độ lớn của tập hợp phản nhị phân lớn nhất bao gồm các số tự nhiên từ ~1~ đến ~N~

Input

Dòng đầu là ~T~ ~(T \le 60)~, số lượng test.

Mỗi dòng tiếp theo là 1 số tự nhiên ~N~ ~(1 \le N \le 100\,000\,000)~

Output

Với mỗi test, in ra 1 dòng là kết quả của test đó

Sample Input

5
11
12
13
14
15

Sample Output

7
8
9
9
10

Ở một quốc gia nọ có một trung tâm cấp nước. Vì việc cung cấp thẳng từ trung tâm cấp nước đến các hộ gia đình rất khó khăn, nên quốc gia này quyết định xây dựng thêm nhiều trung tâm cấp nước khác. Họ quyết định sẽ xây dựng hệ thống cấp nước theo mô hình là một cây có gốc ở trung tâm hiện tại, nước chảy đi theo hướng từ gốc đến lá, các lá sẽ làm nhiệm vụ cung cấp nước cho người dân.

Do bị bóc lột bởi một số thế lực, quốc gia này không có nước sạch trong lòng đất, chỉ có thể dựa vào nước mưa. Mưa có thể xảy ra ở nhiều nơi, khi trời mưa, một số trung tâm cấp nước sẽ ở trong khu vực mưa và sẽ nhận được một lượng mưa nhất định (có thể khác nhau).

Để kiểm soát lượng nước ở các trung tâm cấp nước, người ta muốn bạn giải quyết bài toán sau:

• Ban đầu có duy nhất một trung tâm, nút gốc 1, không có nước.

• Ở mỗi thời điểm, có thể có trung tâm mới đi vào hoạt động. Truy vấn này sẽ được cung cấp dưới dạng:

  + ~u~ ~v~ ~(1 \le u < v)~: Trung tâm ~v~ đi vào hoạt động, với đỉnh cha là trung tâm ~u~. Dữ liệu đảm bảo rằng ~v~ là số nguyên dương nhỏ nhất chưa được dùng để đánh số cho bất kì trung tâm nào khác. Khi trung tâm ~v~ đi vào hoạt động, trung tâm ~v~ không có nước nhưng toàn bộ lượng nước đang có ở trung tâm ~u~ sẽ chảy sang trung tâm ~v~.

• Ở mỗi thời điểm, mưa có thể diễn ra. Truy vấn này có dạng:

  # ~u~ ~k~ ~(1 \le u, 0 < k \le 10^9)~: Mưa xảy ra và trung tâm ~u~ nhận được lượng nước ~k~. Dữ liệu đảm bảo ~u~ là một nút đã được thêm vào cây. Khi một trung tâm ~u~ nhận được nước, nếu trung tâm này không phải là nút lá thì nước sẽ chảy đều đến các trung tâm con.

  • Ví dụ, nếu u có đúng ~2~ con là ~x~ và ~y~ mà mưa đổ ra ở cây con gốc ~u~ thì ~x~ và ~y~ sẽ cùng nhận được lượng nước là ~k/2~. Sau đó nếu ~x~ và ~y~ mà vẫn không phải nút lá thì nước sẽ tiếp tục chảy đến các nút con của chúng.
  • Xem như thời gian để nước chảy là không đáng kể, mỗi khi mưa rơi thì các nút lá sẽ nhận được nước chảy về ngay lập tức.

• Ở mỗi thời điểm, người ta cần biết lượng nước đang có tại một trung tâm nhất định. Truy vấn này có dạng:

  ? ~u~ ~(1 \le u)~: In ra lượng nước đang có ở trung tâm u.

  • Dễ chứng minh được rằng kết quả có thể được biểu diễn dưới dạng ~\frac{P}{Q}~ với ~P~ và ~Q~ là hai số nguyên tố cùng nhau, bạn chỉ cần in ra giá trị ~P \times Q^{-1}~ mod ~(10^9+7)~.

Input format

Chú ý rằng input của bài này đã bị mã hóa.

Cụ thể, tất cả các số ~u, v, k~, trong ~+~ ~u~ ~v~, # ~u~ ~k~, ~?~ ~u~ được cho trong input thực tế là ~u \oplus ans~, ~v \oplus ans~, và ~k \oplus ans~ với ~ans~ là kết quả (giá trị được in ra) của truy vấn ~?~ cuối cùng, ~ans~ ban đầu được gán là 0. (~\oplus~ là bitwise xor).

Input

Dòng đầu tiên là một số nguyên ~n\ (1 \le n \le 3 \times 10^5)~, số lượng truy vấn.

~n~ dòng tiếp theo, mỗi dòng là một truy vấn có dạng đã nêu ở trên.

Output

Với mỗi truy vấn ? in ra kết quả theo dạng đã nêu.

Subtask

• ~30\%~ số điểm có ~n \le 10000~
• ~70\%~ còn lại không có điều kiện gì thêm.

Sample Input

16
+ 1 2
+ 1 3
# 1 2
? 3
# 0 2
? 3
+ 500000004 500000002
+ 500000004 500000003
? 500000002
? 500000003
# 1 4
? 1
? 2
? 3
? 500000012
? 500000002

Sample Output

1
500000006
500000006
0
0
0
500000008
500000007
1

Note

Input không mã hóa:

16
+ 1 2
+ 1 3
# 1 2
? 3
# 1 3
? 2
+ 2 4
+ 2 5
? 4
? 5
# 1 4
? 1
? 2
? 3
? 4
? 5

Lượng nước có trong mỗi trung tâm (ban đầu và sau mỗi truy vấn):

[0]
[0, 0]
[0, 0, 0]
[0, 1, 1]
[0, 1, 1]
[0, 2.5, 2.5]
[0, 2.5, 2.5]
[0, 0, 2.5, 2.5]
[0, 0, 2.5, 2.5, 0]
[0, 0, 2.5, 2.5, 0]
[0, 0, 2.5, 2.5, 0]
[0, 0, 4.5, 3.5, 1]
[0, 0, 4.5, 3.5, 1]
[0, 0, 4.5, 3.5, 1]
[0, 0, 4.5, 3.5, 1]

Cho ~n~ là một số ngẫu nhiên trong đoạn ~[A,B]~ với ~A~, ~B~ là 2 số nguyên dương và ~(1 \le A \le B \le 10^9)~. Chemthan và RR chơi 1 trò chơi với ~n~ tờ giấy được viết số 1 trên bàn. Ở mỗi lượt chemthan sẽ chọn 2 tờ giấy viết số ~x~, ~y~ trên bàn, RR sẽ bỏ 2 tờ giấy này vào sọt rác và thay thế bằng tờ giấy viết giá trị ~x + y~ hoặc ~|x - y|~.

Trò chơi sẽ dừng nếu 1 trong 2 trường hợp xảy ra:

• Có 1 số lớn hơn tổng của tất cả những số còn lại
• Tất cả các số đều bằng 0

Cuối cùng RR phải dọn các tờ giấy này nên RR muốn số lượng giấy còn lại trên bàn là nhỏ nhất còn chemthan muốn số lượng là lớn nhất. In ra kết quả là expected số lượng giấy RR phải dọn nếu cả 2 đều chơi tối ưu. Có thể chứng minh được kết quả là một phân số ~P/Q~ (với ~P~,~Q~ nguyên tố cùng nhau) cần in ra giá trị ~P \times Q^{-1}~ mod ~(10^9+7)~

Input

• Gồm một dòng 2 số ~A~, ~B~

Output

• Kết quả của bài toán

Sample Input 1

2 2

Sample Output 1

1

Sample Input 2

2 3

Sample Output 2

500000005

Subtask

• ~40\%~ số test có ~1 \le A \le B \le 100~
• ~60\%~ số test có ~1 \le A \le B \le 10^9~

Vào năm 3021, lúc này loài người đã sinh sống ở ~n + 1~ hành tinh khác nhau, được đánh số từ ~0~ tới ~n~. Điều đặc biệt là tất cả hành tinh này đều nằm trên một đường thẳng. Hành tinh thứ ~i~ cách hành tinh thứ ~(i-1)~ một khoảng là ~a[i]~ năm ánh sáng.

Bạn là một shipper liên hành tinh, hiện tại bạn đang đứng ở hành tinh ~0~ và cần ship ~n~ gói hàng cho ~n~ hành tinh còn lại. Bạn cần đưa ~n~ gói hàng cho ~n~ hành tinh theo đúng thứ tự từ ~1~ tới ~n~.

Dụng cụ bạn được cung cấp là một con tàu có khả năng thực hiện cú nhảy alpha. Với mỗi lần nhảy, con tàu sẽ dịch chuyển tức thời lên phía trước một khoảng bằng ~1~ năm ánh sáng trong ~1~ giây. Hiện nay, ở mỗi hành tinh (kể cả hành tinh ~0~) đều cung cấp một gói nâng cấp tàu vũ trụ: bạn có thể tăng khoảng cách dịch chuyển của con tàu trong một lần nhảy lên một số nguyên dương bất kỳ (tính theo năm ánh sáng). Lưu ý rằng một khi đã tăng thì bạn sẽ không có thể giảm khoảng cách dịch chuyển xuống. Nếu bạn tăng khoảng cách dịch chuyển quá lớn, điều đó có thể dẫn tới việc bạn nhảy lố khỏi hành tinh tiếp theo cần tới. Bạn cũng không thể dịch chuyển ngược về các hành tinh trước.

Với một chiến thuật tăng tốc hợp lý, hãy tính số giây ít nhất mà bạn cần để có thể giao ~n~ gói hàng cho ~n~ hành tinh.

Input

• Dòng đầu tiên chứa số ~n~ là số hành tinh.
• Dòng tiếp theo chứa ~n~ số là khoảng cách ~a[i]~ giữa các hành tinh.

Output

• Số giây ít nhất để giao ~n~ gói hàng

Sample Input

4
4 2 4 7

Sample Output

5

Subtask

• ~30\%~ số test có ~1 \le n \le 3000~, ~1 \le a[i] \le 3000 \; \forall i \in [1; n]~
• ~70\%~ số test còn lại ~1 \le n \le 100000~, ~1 \le a[i] \le 100000 \; \forall i \in [1; n]~

Note

• Ở hành tinh 0, bạn tăng tốc độ của tàu lên 2. Sau đó nhảy 2 lần để tới hành tinh 1 (khoảng cách 4). Thời gian: 2 giây
• Ở hành tinh 1, bạn giữ nguyên tốc độ, nhảy 1 lần tới hành tinh 2 (khoảng cách 2). Thời gian: 1 giây
• Ở hành tinh 2, bạn tăng tốc độ lên 4. Sau đó nhảy 1 lần để tới hành tinh 3 (khoảng cách 4). Thời gian: 1 giây.
• Ở hành tinh 3, bạn tăng tốc độ lên 7. Sau đó nhảy 1 lần để tới hành tinh 4 (khoảng cách 7). Thời gian: 1 giây.
• Tổng thời gian: ~2 + 1 + 1 + 1 = 5~

Lưu ý rằng ở hành tinh 0 bạn không thể tăng tốc độ lên 4, vì nếu tăng lên 4 thì bạn sẽ không có cách nào để nhảy từ hành tinh 1 tới hành tinh 2 (với khoảng cách là 2).

Có một dãy số nguyên không âm ~a_1, a_2,..., a_N~.

Cho ~K~ dữ kiện, mỗi dữ kiện gồm 4 số nguyên ~l, r, X, Y~ cho biết rằng ~X \le \sum_{i=l}^{r} a_i \le Y~.

Đặt ~f(a) = \sum_{i=1}^{N} a_i \times i~.

Tìm dãy số ~a~ thỏa mãn tất cả ~K~ dữ kiện sao cho ~f(a)~ đạt giá trị nhỏ nhất.

Input:

• Dòng đầu tiên chứa 2 số nguyên ~N~, ~K~.
• ~K~ dòng tiếp theo, mỗi dòng chứa 1 dữ kiện gồm 4 số nguyên ~l, r, X, Y~ (~1 \le l \le r \le N~, ~0 \le X \le Y \le 2 \times 10^{10}~).

Output:

• Nếu không tồn tại dãy a thỏa mãn tất cả các dữ kiện, in ra duy nhất ~-1~. Ngược lại in ra ~N~ số nguyên không âm là dãy ~a~ tìm được. Nếu có nhiều đáp án chỉ cần in ra một đáp án bất kỳ.

Sample input 1

7 5
4 5 3 4
2 6 25 25
3 5 7 8
3 5 6 8
2 4 12 13

Sample output 1

0 10 3 0 4 8 0 

Sample input 2

2 2
1 2 1 2
1 1 3 3

Sample output 2

-1

Scoring:

• Subtask 1 (20%): ~1 \le N, K \le 100~.
• Subtask 2 (80%): ~1 \le N, K \le 10000~.

Cho 2 số nguyên dương ~a,m~ tìm một số nguyên dương ~x \leq 10^{18}~ sao cho ~a^x \equiv x~ (mod ~m~), nếu không tìm được in ra ~-1~.

Input

Dòng đầu tiên chứa 2 số nguyên dương ~a, m~.

Output

Một số nguyên dương ~x~ duy nhất. Nếu có nhiều ~x~ thỏa mãn, bạn có thể in ~x~ bất kỳ.

Ví dụ:

Input:

3 5

Output:

7

Subtask

• Subtask #1: ~50\%~ ~1 \leq a, m \leq 10^3~.
• Subtask #2: ~50\%~ ~1 \leq a, m \leq 10^9~.

Cho ~x_1, x_2, …., x_n~. Định nghĩa hàm ~f~ như sau:

• ~f(y_1) = y_1~.
• ~f(y_1, y_2) = y_1^{y_2}~.
• ~f(y_1, y_2, y_3) = y_1{^{y_2^{y_3}}}~.
• ~f(y_1, y_2, …, y_k) = y_1^{f(y_2, …, y_k)}~.

Tính tổng ~f(x_i,x_{i+1},..., x_j)~ qua tất cả các bộ ~1\leq i\leq j\leq n~ trong modulo ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~
• Dòng thứ 2 chứa ~n~ số nguyên ~x[i]~.

Output

• Tổng ~f(x_i,x_{i+1},..., x_j)~ trong modulo ~10^9+7~.

Sample Input:

5
1 5 9 2 2

Sample Output

409983298

Subtask

Giới hạn: ~1\leq N\leq 10^4, 1\leq x_i\leq 10^9~.

• ~50\%~ số điểm có ~1 \leq n \leq 10^2~.
• ~50\%~ số điểm còn lại có ~1 \leq n \leq 10^4~.

Cho ~N~ cái kẹo với khối lượng lần lượt là ~W_1, W_2,..., W_N~ kg.

Gọi ~f_{ab}~ là số viên kẹo nhiều nhất có thể đựng được trong ~2~ túi mà mỗi túi có thế tối đa mang được ~a~ và ~b~ kg. Tính tổng ~(f_{ij}\ \oplus \ i\ \oplus\ j)~ qua tất cả các bộ ~1 \leq i, j \leq 5\cdot 10^3~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~
• Dòng thứ 2 chứa ~N~ số nguyên ~W_i~.

Output

• Tổng ~(f_{ij}\ \oplus \ i\ \oplus\ j)~ qua tất cả các bộ ~1 \leq i, j \leq 5\cdot 10^3~

Sample Input:

5
1 2 3 4 5

Sample Output:

80285361774

Subtask

Giới hạn: ~1\leq N, W_i \leq 5\cdot 10^3~.

• ~50\%~ số điểm có ~1 \leq N, W_i \leq 10^2~.
• Có ~50\%~ số điểm còn lại có ~1 \leq N, W_i \leq 5\cdot 10^3~.

Một máy tính cần chạy ~N~ tasks đánh số từ ~1-N~, mỗi task khi chạy sẽ có một số dữ liệu input và output. Mỗi dữ liệu được đặt tên là một chuỗi bao gồm chữ cái in thường, số và dấu "_". Dữ liệu input của một task sẽ là dữ liệu output của một task khác và được xác định bằng một số integer - biểu thị ID của task chứa dữ liệu output và một chuỗi là tên của dữ liệu output tương ứng.

Ví dụ:

Task 1:
Input:
Output: data_x data_y data_z
Task 2:
Input: (1, data_x)
Output: output_z
Task 3:
Input: (2, output_z)
Output:

Cho thông tin về input và output của các task, in ra thứ tự thực hiện các task, biết rằng nếu một task ~A~ sử dụng dữ liệu output của task ~B~ thì máy tính cần sắp xếp sao cho task ~A~ chạy sau task ~B~. In ra ~Impossible~ nếu không có thứ tự hợp lí, nếu có nhiều thứ tự thì in ra task có thứ tự từ điển lớn nhất.

Input:

• Dòng đầu tiên là một số nguyên dương ~T~, số lượng test cần phải giải quyết.
• Mỗi nhóm trong số ~T~ dòng sau là một test có dạng như sau:
  • Dòng đầu tiên là một số nguyên dương ~N~. Các dòng tiếp theo mô tả thông tin về các task.
• Mỗi task sẽ được mô tả như sau:
  • Dòng thứ nhất chứa một số nguyên ~O~ và ~O~ chuỗi độ dài không quá 5 liệt kê output của task.
  • Dòng thứ hai chứa một số nguyên ~I~ là số lượng input của task, ~I~ dòng kế tiếp mỗi dòng chứa một số nguyên và một chuỗi, biểu thị ID và tên của dữ liệu input.

Output:

Với mỗi test in ra một dòng chứa N số nguyên biểu thị thứ tự cần tìm hoặc ~Impossible~ nếu không có thứ tự hợp lý.

Subtask:

• ~1/3~ số test có ~1 \le T \le 10~, ~1 \le N \le 100~
• ~2/3~ số test còn lại có ~1 \le T \le 10~, ~1 \le N \le 5000~
• Tên dữ liệu là một chuỗi độ dài không quá 10 kí tự, bao gồm chữ cái in thường, số và dấu.

Sample Input 1:

1
3
3 data_x data_y data_z
0
1 output_z
1
1 data_x
0
1
2 output_z

Sample Output 1:

1 2 3

Sample Input 2:

1
2
1 data_xyz
1
2 data_abc
1 data_abc
1
1 data_xyz

Sample Output 2:

Impossible

Cho ma trận ~X[n\times d]~ và vector ~y[n]~, tìm vector ~c[d]~ sao cho:

1. Đặt ~E=X\times c-y~, thì ~\sqrt{\sum{E_{ij}^2}}~ là nhỏ nhất (còn gọi là norm ~l_2~ của ~E~)
2. ~\sqrt{\sum{c_i^2}}~ là nhỏ nhất (còn gọi là norm ~l_2~ của ~c~).

Ưu tiên vector ~c~ tối ưu bước ~1~ trước, trong trường hợp có nhiều vector ~c[d]~ có giá trị norm ~l_2~ của ~E~ bằng nhau thì chọn vector ~c~ có norm ~l_2~ nhỏ nhất theo bước ~2~.

Input

Dòng thứ nhất chứa ~n, d~.

~n~ dòng tiếp theo, mỗi dòng chứa ~d~ số nguyên của ma trận ~X~.

Dòng tiếp theo chứa ~n~ số nguyên của vector ~y~.

Output

In ra ~c_1, c_2, ..., c_d~ trên một dòng. Kết quả của bạn được xem là đúng nếu như kết quả của bạn có chênh lệch không quá ~10^{-6}~ với đáp án.

Giới hạn: ~1\leq N,D\leq 500,\ |X_{ij}|\leq 10^3,\ |y_i|\leq 10^3~, dữ liệu được tạo ra ngẫu nhiên (trừ test ví dụ).

Subtask #1: ~50\%~ ~1\leq N,D\leq 50~.

Subtask #2: ~50\%~ ~1\leq N,D\leq 500~.

Ví dụ:

Input:

1 2
1 1  
1

Output:

0.500000000 0.500000000