Năm Covid thứ nhất, Giáo sư Kẻ-là-ai-cũng-biết-là-ai-đấy - một KOL nổi tiếng trong làng VNOI đã buồn phải ở nhà không được đi chơi.

Tất nhiên để giải sầu, giáo sư sẽ post bài trên facebook. Giáo sư có rất nhiều chủ đề: thả thính, cách ly, đồ bảo hộ,… Tuy nhiên là người điều độ, một ngày giáo sư post đúng \(n\) bài.

Kế hoạch của giáo sư được định nghĩa là một tập hợp các số tự nhiên được sắp xếp, có thứ tự \((p_1, p_2, …, p_k)\), chứa ít nhất hai phần tử, thỏa mãn điều kiện: \(p_1 + p_2 + ... + p_k = n\). Kế hoạch này thể hiện giáo sư sẽ post \(p_1\) bài chủ đề \(1\), \(p_2\) bài chủ đề \(2\), … , \(p_k\) bài chủ đề \(k\).

Giáo sư sẽ liệt kê tất cả các kế hoạch của mình theo thứ tự từ điển.

Ví dụ: đối với nếu \(n = 4\), giáo sư có \(7\) kế hoạch, liệt kê trong bảng từ điển như sau:

\(\begin{matrix} &Số\ thứ\ tự &Kế\ hoạch\\ &1&1\ 1\ 1\ 1\\&2&1\ 1\ 2 \\&3&1\ 2\ 1\\&4&1\ 3\\&5&2\ 1\ 1\\&6&2\ 2\\&7&3\ 1\end{matrix}\)

Biết giá trị của số tự nhiên \(n\).

1. Với số \(k\) cho trước, giúp giáo sư xác định kế hoạch post bài có vị trí \(k\) trong bảng từ điển.
2. Với một kế hoạch nhất định, tính vị trí của nó trong bảng từ điển của giáo sư.

Input

• Dòng đầu tiên ghi số \(c\) (\(1\) hoặc \(2\)) là nhiệm vụ cần giải quyết.
• Dòng thứ hai ghi giá trị số \(n\).
• Dòng thứ ba, tùy thuộc vào giá trị của \(c\), ghi:
  • Nếu \(c = 1\), số tự nhiên \(k\),
  • Nếu \(c = 2\), các số tự nhiên cách nhau bởi một khoảng trắng là một kế hoạch của giáo sư.

Output

• In ra đáp án.

Constraints

• \(1 < n < 10.000\).
• \(0 < k < 10^{17}\) (dù \(c = 1\) hay \(c = 2\)).
• Đảm bảo có đáp án

Scoring

• Subtask \(1\) (\(18\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(36\%\) số điểm): \(n <10 000\) và \(k \le 1 000 000\)
• Subtask \(3\) (\(18\%\) số điểm): \(k \le 2 000 000 000\)

Example

1
4
5 

2 1 1

2
21
1 2 3 4 5 6 

375776