Περιγραφή προβλήματος

Επειδή το CCO χρησιμοποιεί συχνά ακέραιους αριθμούς, η Alice πρέπει να μάθει για τους ακέραιους αριθμούς! Ένας θετικός ακέραιος αριθμός ~n~ μπορεί να γραφτεί στη βάση ~b~ ως η ακολουθία ~d_{m-1}d_{m-2}\ldots d_1d_0~, αν ισχύουν τα ακόλουθα:

• Κάθε ψηφίο ~d_i~ βρίσκεται μεταξύ ~0~ και ~b-1~, συμπεριλαμβανομένων των άκρων.

• ~d_{m-1} > 0~.

• ~n = d_{m-1} \times b^{m-1} + d_{m-2} \times b^{m-2} + \cdots + d_1 \times b^1 + d_0 \times b^0~.

Για παράδειγμα, ο ακέραιος αριθμός ~2025~ στη βάση ~19~ είναι η ακολουθία ~(5, 11, 11)~, επειδή ~2025 = 5 \times 19^2 + 11 \times 19^1 + 11 \times 19^0~.

Ένας ακέραιος αριθμός ~n~ λέγεται ισορροπημένος στη βάση ~b~ αν, όταν γραφτεί στη βάση ~b~, ο μέσος όρος των ψηφίων του είναι ~\frac{b-1}{2}~.

Για παράδειγμα, ο αριθμός ~2025~ είναι ισορροπημένος στη βάση ~19~, επειδή ~\frac{5+11+11}{3} = 9 = \frac{19-1}{2}~.

Η Alice μπορεί εύκολα να βρει ακέραιους αριθμούς που είναι ισορροπημένοι στη βάση ~19~. Ωστόσο, δυσκολεύεται να βρει ακέραιους αριθμούς που είναι ισορροπημένοι με πολλούς διαφορετικούς τρόπους. Δεδομένων των ~B~ και ~N~, βοηθήστε την Alice να βρει τον ελάχιστο ακέραιο αριθμό ~x~ ώστε:

• Ο ~x~ να είναι ισορροπημένος στη βάση ~b~, για κάθε ~2 \le b \le B~.

• ~x \ge N~.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους αριθμούς ~B~ και ~N~, χωρισμένους με ένα κενό (~N \ge 1~).

Εγγυάται ότι η απάντηση δεν υπερβαίνει το ~10^{18}~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμοι 25 βαθμοί:

Βαθμοί	Όρια του B	Όρια του N
2	~2 \le B \le 7~	~1 \le N \le 10^4~
6	~2 \le B \le 6~	~N = 10^{10}~
2	~2 \le B \le 7~	Χωρίς πρόσθετους περιορισμούς
9	~8 \le B \le 11~	~N = 1~
4	~B = 8~	Χωρίς πρόσθετους περιορισμούς
2	~9 \le B \le 11~	Χωρίς πρόσθετους περιορισμούς

Έξοδος

Εκτυπώστε τον ελάχιστο ακέραιο αριθμό ~x~ που περιγράφεται στην εκφώνηση.

Παράδειγμα 1

Είσοδος

4 100

Έξοδος

141

Επεξήγηση εξόδου

Ο αριθμός ~141~ στη βάση ~2~ είναι ~10001101~. Ο μέσος όρος των ψηφίων είναι ~\frac{1+0+0+0+1+1+0+1}{8} = 0.5 = \frac{2-1}{2}~. Επομένως, ο ~141~ είναι ισορροπημένος στη βάση ~2~.

Ο αριθμός ~141~ στη βάση ~3~ είναι ~12020~. Ο μέσος όρος των ψηφίων είναι ~\frac{1+2+0+2+0}{5} = 1 = \frac{3-1}{2}~. Επομένως, ο ~141~ είναι ισορροπημένος στη βάση ~3~.

Ο αριθμός ~141~ στη βάση ~4~ είναι ~2031~. Ο μέσος όρος των ψηφίων είναι ~\frac{2+0+3+1}{4} = 1.5 = \frac{4-1}{2}~. Επομένως, ο ~141~ είναι ισορροπημένος στη βάση ~4~.

Τέλος, ~141 \ge 100~.

Παράδειγμα 2

Είσοδος

7 10000000000

Έξοδος

16926961207710

Υπόδειξη

Μπορείτε να χρησιμοποιήσετε τα παρακάτω αποσπάσματα κώδικα ως μέρος της λύσης σας.

// Σημαντικό: Αν το x είναι 0, το αποτέλεσμα δεν ορίζεται.
int base_2_length(unsigned long long x) {
    return 64-__builtin_clzll(x);
}
int base_2_sum(unsigned long long x) {
    return __builtin_popcountll(x);
}