Bài tập

Tập đoàn công nghệ XYZ yêu cầu bạn tạo ra tất cả các chuỗi ngoặc hợp lệ (đúng) có độ dài \(2N\), trong đó có \(N\) cặp dấu ngoặc đơn \(\text{'('}\) và \(\text{')'}\). Một chuỗi ngoặc là hợp lệ nếu: 1) Số lượng \(\text{'('}\) bằng số lượng \(\text{')'}\) và 2) Với mọi tiền tố, số lượng \(\text{'('}\) luôn \(\ge\) số lượng \(\text{')'}\).

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 8\)).

Output

In ra tất cả các chuỗi ngoặc hợp lệ có \(N\) cặp ngoặc, mỗi chuỗi trên một dòng, theo thứ tự từ điển tăng dần.

Example

1

()

2

(())
()()

Cân thằng bằng đã từng rất phổ biến trong xã hội loài người, vì tính đơn giản của nó. Cấu tạo của cân gồm hai đĩa \(A, B\) được đặt ở hai đầu của một đòn bẩy.

Có \(n\) quả cân, quả thứ \(i\) có khối lượng \(m_i\). Để cân một vật, người ta đặt nó vào đĩa \(A\), sau đó thêm một vài quả cân vào các đĩa sao cho cân thăng bằng. Lúc này, cân nặng của vật là tổng khối lượng các quả cân trên đĩa \(B\) trừ đi tổng khối lượng các quả cân trên đĩa \(A\), vì cân chỉ thăng bằng khi tổng khối lượng trên đĩa \(A\) bằng tổng khối lượng trên đĩa \(B\).

Tuần trước, con chim vừa chở người em đi lấy vàng về, người em tiến hành cân lại số vàng mình nhận được. Để thuận tiện, anh ấy sẽ để nguyên túi vàng và cân một lần thay vì phải tách số vàng ra. Sau khi cân, anh ấy biết chính xác rằng túi vàng nặng \(M\).

Sau đó, vì tò mò và đam mê thuật toán, anh ấy thắc mắc là liệu có bao nhiêu cách cân khác nhau? Cụ thể hơn, bạn được cho một vật có khối lượng \(M\), bạn đặt nó vào đĩa \(A\) sau đó thêm một số quả cân vào các đĩa sao cho cân thăng bằng. Cần đếm số cách khác nhau để thêm các quả cân như trên. Hai cách được coi là khác nhau nếu tồn tại \(i\), \(1 ≤ i ≤ n\), sao cho hoặc là trong cách này thì sử dụng quả cân thứ \(i\) còn trong cách kia thì không, hoặc là cả hai cách đều sử dụng quả cân thứ \(i\) nhưng đặt vào hai đĩa khác nhau.

Input

• Dòng đầu chứa: \(n, M\)

• Dòng tiếp theo chứa dãy \(m\)

Output

• Một số nguyên duy nhất là kết quả bài toán

Example

6 10
1 2 3 4 5 6

17

Ban đầu, chị Cam có \(A\) viên bi, em Dino có \(B\) viên bi. Mỗi ngày chị Cam cho em Dino đúng \(1\) viên bi, đến khi chị Cam hết bi thì chị không cho nữa.

Yêu cầu: Hỏi ngày thứ \(N\) thì chênh lệch số bi của hai chị em là bao nhiêu?

Input

• Nhập vào ba số tự nhiên \(A, B, N\) (\(1 \leq A, B, N \leq 10^9\)). Mỗi số trên một dòng

Output

• Ghi ra một số tự nhiên duy nhất là kết quả của bài toán.

Example

7
4
1

1

4
7
1

5

2
4
3

6

Công chúa con vua xứ Flatland chuẩn bị làm đám cưới với một hoàng tử xinh đẹp của nước láng giềng. Vua cha dự định sẽ dành cho con gái yêu một món quà hồi môn ấn tượng, đó là một phần dộ sưu tập đá quý của mình. Nhà vua có bộ sưu tập \(n\) viên đá quý, đánh số từ \(1\) đến \(n\). Viên thứ \(i\) có trọng lượng \(w_i\) và giá trị \(v_i\). Nhà vua muốn món quà càng có giá trị càng tốt nhưng trọng lượng cũng phải ở mức hợp lý -- chỉ trong khoảng từ \(L\) đến \(R\).
Yêu cầu: Hãy chỉ ra cách chọn các viên đá quý thỏa mãn điều kiện của nhà vua.

Input

• Dòng đầu tiên chứa \(3\) số nguyên \(n, L\) và \(R\) \((1 \le n \le 32, 0 \le L \le R \le 10^{18})\)

• Dòng thứ \(i\) trong \(n\) dòng sau chứa \(2\) số nguyên \(w_i\) và \(v_i\) \((1 \le w_i, v_i \le 10^{15})\).

Output

• Dòng đầu tiên đưa ra số nguyên \(k\) -- số viên đá được chọn.

• Mỗi dòng trong \(k\) dòng sau chứa số nguyên trong phạm vi từ \(1\) đến \(n\) xác định viên đá được chọn.

Nếu không thể chọn được món quà đạt yêu cầu thì đưa ra một dòng chứa số \(0\).

Example

3 6 8
3 10
7 3
8 2

1
2