Nhập vào một số nguyên dương ~n~ (~1 \le n \le 10^{10}~), hãy in ra giá trị ~n+1~.

Dưới đây là đoạn mã C++ giải bài toán trên, tuy nhiên lời giải này sẽ sai trong một số trường hợp.

Nhiệm vụ của bạn là hãy in ra ~10~ giá trị sai bất kì.

Lưu ý: đoạn code dưới đây đã được mã hóa.

#define qicWrIju abcshjadahsdbahsdbhbc(s);
#define ZVu819uW (i
#define Qm9FO1B4 +
#define rPXSPONB 52
#define ujtR1Zn9 long
#define IDphavfB 1292391ll
#define W1P4iS7p xdewddqwd)
#define ITlw9gr7 -
#define O9bvufKM n){
#define wtG9yVmP set<long
#define q4MQnZ1l (36
#define JBs4UCQY *
#define MYjaa6Sk i
#define dvS37aaf %
#define YjXuMId5 17
#define HIotfhMy }
#define swH6EF3X n
#define u1A9vIKd abjnsdhdahsdhasdas.end())
#define ZGIKJryh n;
#define PkkHVmri i++)
#define oWbA679q (int)sqrt(26))
#define AfP1laNE (((xdewddqwd
#define WsyvurbC for
#define k44VO6RG (int)sqrt(26));
#define wj9JSWQM 39
#define xAwkdHwI 99
#define arvWdpAx 44;
#define lKnUILxP (int
#define B1Dt1qld abcshjadahsdbahsdbhbc(long
#define XL70c8Qt if
#define r9Mu1U4k s
#define xI3rruny 37
#define TsrWQd7R 33
#define L4rP77c1 prep()
#define ytu5A5FX void
#define vXRdv7Zg ((int)(sqrt(10001)))
#define RoIFPg9q <=
#define sMPIckAa solve(long
#define PJfMTaCg 10000000000ll;
#define THBkV7MA <<
#define LkWKAiwN abjnsdhdahsdhasdas.insert(s);
#define SUnJ9GKB 1ll
#define GJ3fgYO2 (abjnsdhdahsdhasdas.find(n)
#define ltdbtp6d return
#define GXPqGAD0 long>
#define Jwpuw0G4 3312881ll)
#define qHajqNUb {
#define WesmXntD 0)
#define aMKkMFJL 123911ll)
#define L9JrAU5Z 13
#define SrD71jWj 1;
#define Ebk9bRJh 4ll)
#define cviVwZnB abjnsdhdahsdhasdas;
#define qEfJreEg 69
#define bIUS9Tlh !=
#define LhjLM2BZ ==
#define f0Hd7Klb =
wtG9yVmP GXPqGAD0 cviVwZnB ujtR1Zn9 ujtR1Zn9 B1Dt1qld ujtR1Zn9 W1P4iS7p qHajqNUb ltdbtp6d AfP1laNE 
JBs4UCQY IDphavfB dvS37aaf aMKkMFJL THBkV7MA Ebk9bRJh JBs4UCQY Jwpuw0G4 dvS37aaf PJfMTaCg HIotfhMy 
ytu5A5FX L4rP77c1 qHajqNUb ujtR1Zn9 ujtR1Zn9 r9Mu1U4k f0Hd7Klb L9JrAU5Z JBs4UCQY wj9JSWQM JBs4UCQY 
SUnJ9GKB JBs4UCQY SUnJ9GKB JBs4UCQY SUnJ9GKB Qm9FO1B4 YjXuMId5 JBs4UCQY rPXSPONB Qm9FO1B4 xAwkdHwI 
JBs4UCQY TsrWQd7R Qm9FO1B4 xI3rruny JBs4UCQY arvWdpAx WsyvurbC lKnUILxP MYjaa6Sk f0Hd7Klb SrD71jWj 
MYjaa6Sk RoIFPg9q q4MQnZ1l Qm9FO1B4 qEfJreEg ITlw9gr7 oWbA679q JBs4UCQY q4MQnZ1l Qm9FO1B4 qEfJreEg 
ITlw9gr7 k44VO6RG PkkHVmri qHajqNUb r9Mu1U4k f0Hd7Klb qicWrIju XL70c8Qt ZVu819uW dvS37aaf vXRdv7Zg 
LhjLM2BZ WesmXntD LkWKAiwN HIotfhMy HIotfhMy ujtR1Zn9 ujtR1Zn9 sMPIckAa ujtR1Zn9 O9bvufKM XL70c8Qt 
GJ3fgYO2 bIUS9Tlh u1A9vIKd qHajqNUb ltdbtp6d ZGIKJryh HIotfhMy ltdbtp6d swH6EF3X Qm9FO1B4 SrD71jWj 
HIotfhMy

Cách tìm ra các giá trị trên

/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int Rand(int l, int r){
    return uniform_int_distribution<int>(l, r)(rng);
}

#define qicWrIju abcshjadahsdbahsdbhbc(s);
#define ZVu819uW (i
#define Qm9FO1B4 +
#define rPXSPONB 52
#define ujtR1Zn9 long
#define IDphavfB 1292391ll
#define W1P4iS7p xdewddqwd)
#define ITlw9gr7 -
#define O9bvufKM n){
#define wtG9yVmP set<long
#define q4MQnZ1l (36
#define JBs4UCQY *
#define MYjaa6Sk i
#define dvS37aaf %
#define YjXuMId5 17
#define HIotfhMy }
#define swH6EF3X n
#define u1A9vIKd abjnsdhdahsdhasdas.end())
#define ZGIKJryh n;
#define PkkHVmri i++)
#define oWbA679q (int)sqrt(26))
#define AfP1laNE (((xdewddqwd
#define WsyvurbC for
#define k44VO6RG (int)sqrt(26));
#define wj9JSWQM 39
#define xAwkdHwI 99
#define arvWdpAx 44;
#define lKnUILxP (int
#define B1Dt1qld abcshjadahsdbahsdbhbc(long
#define XL70c8Qt if
#define r9Mu1U4k s
#define xI3rruny 37
#define TsrWQd7R 33
#define L4rP77c1 prep()
#define ytu5A5FX void
#define vXRdv7Zg ((int)(sqrt(10001)))
#define RoIFPg9q <=
#define sMPIckAa solve(long
#define PJfMTaCg 10000000000ll;
#define THBkV7MA <<
#define LkWKAiwN abjnsdhdahsdhasdas.insert(s);
#define SUnJ9GKB 1ll
#define GJ3fgYO2 (abjnsdhdahsdhasdas.find(n)
#define ltdbtp6d return
#define GXPqGAD0 long>
#define Jwpuw0G4 3312881ll)
#define qHajqNUb {
#define WesmXntD 0)
#define aMKkMFJL 123911ll)
#define L9JrAU5Z 13
#define SrD71jWj 1;
#define Ebk9bRJh 4ll)
#define cviVwZnB abjnsdhdahsdhasdas;
#define qEfJreEg 69
#define bIUS9Tlh !=
#define LhjLM2BZ ==
#define f0Hd7Klb =
wtG9yVmP GXPqGAD0 cviVwZnB ujtR1Zn9 ujtR1Zn9 B1Dt1qld ujtR1Zn9 W1P4iS7p qHajqNUb ltdbtp6d AfP1laNE 
JBs4UCQY IDphavfB dvS37aaf aMKkMFJL THBkV7MA Ebk9bRJh JBs4UCQY Jwpuw0G4 dvS37aaf PJfMTaCg HIotfhMy 
ytu5A5FX L4rP77c1 qHajqNUb ujtR1Zn9 ujtR1Zn9 r9Mu1U4k f0Hd7Klb L9JrAU5Z JBs4UCQY wj9JSWQM JBs4UCQY 
SUnJ9GKB JBs4UCQY SUnJ9GKB JBs4UCQY SUnJ9GKB Qm9FO1B4 YjXuMId5 JBs4UCQY rPXSPONB Qm9FO1B4 xAwkdHwI 
JBs4UCQY TsrWQd7R Qm9FO1B4 xI3rruny JBs4UCQY arvWdpAx WsyvurbC lKnUILxP MYjaa6Sk f0Hd7Klb SrD71jWj 
MYjaa6Sk RoIFPg9q q4MQnZ1l Qm9FO1B4 qEfJreEg ITlw9gr7 oWbA679q JBs4UCQY q4MQnZ1l Qm9FO1B4 qEfJreEg 
ITlw9gr7 k44VO6RG PkkHVmri qHajqNUb r9Mu1U4k f0Hd7Klb qicWrIju XL70c8Qt ZVu819uW dvS37aaf vXRdv7Zg 
LhjLM2BZ WesmXntD LkWKAiwN HIotfhMy HIotfhMy ujtR1Zn9 ujtR1Zn9 sMPIckAa ujtR1Zn9 O9bvufKM XL70c8Qt 
GJ3fgYO2 bIUS9Tlh u1A9vIKd qHajqNUb ltdbtp6d ZGIKJryh HIotfhMy ltdbtp6d swH6EF3X Qm9FO1B4 SrD71jWj 
HIotfhMy

void PROGRAM(int _){
    prep();

    set<int> s;

    while (s.size() < 10) {
        int n = Rand(1, 10000000000);
        int v = solve(n);
        if (v != n + 1) {
            s.insert(v);
            cout << v << " " << s.size() << endl;
        } 
    }

    for (auto v : s) cout << v << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

Hãy chạy đoạn code trên ở máy và và submit lên hệ thống ~10~ giá trị bất kì mà đoạn code trên chạy sai.

Cho một dãy ~a~ gồm ~n~ phần tử.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~[l,r,x]~, yêu cầu hãy đếm xem có bao nhiêu ~a_i~ với ~i \in [l,r]~ thỏa mãn ~a_i~ là ước hoặc bội của ~x~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~l,r,x~

Constraints

• ~1 \le n,q \le 2\times10^5~
• ~1 \le a_i \le 2\times10^5~

Output

• Với mỗi truy vấn, in ra kết quả.

Sample Input 1:

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

Sample Output 1:

6 1 3 1 2 

Là sinh viên ngành Công nghệ thông tin, Nam thường xuyên rèn luyện tư duy và kĩ năng lập trình bằng các bài toán lập trình thi đấu. Một bài toán thú vị mà Nam đang suy nghĩ để giải như sau:

Cho ~n~ đoạn số nguyên trên trục số, đoạn thứ ~k~ ~(1 \le k \le n)~ có đầu mút bên trái là ~L_k~, đầu mút bên phải là ~R_k~ và có trọng số là ~w_k~. Với ~a,b~ là hai số nguyên, trọng số của ~(a,b)~ được tính bằng tổng trọng số của tất cả các đoạn ~t~ mà ~a \le L_t \le R_t \le b~ với ~1 \le t \le n~. Cần tìm số nguyên ~(a,b)~ có trọng số lớn nhất.

Yêu Cầu: Cho ~n~ đoạn số, gọi ~S~ là trọng số của cặp số nguyên ~(a,b)~ có trọng số là lớn nhất, hãy giúp Nam xác định giá trị ~S~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~.
• Dòng thứ ~k~ ~(1 \le k \le n)~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~L_k,R_k,w_k~ mô tả đoạn thứ ~k~ ~(1 \le L_k \le R_k \le 10^6; |w_k| \le 10^6)~

Subtask

• Có ~30\%~ số test có: ~n \le 200~.
• Có ~30\%~ số test có: ~n \le 2000~.
• Có ~20\%~ số test có: ~R_1 - L_1 = R_2 - L_2 = ... = R_n - L_n~ và ~n \le 10^5~.
• Có ~20\%~ số test có: ~n \le 10^5~.

Output

• Gồm một số nguyên ~S~ là trọng số lớn nhất tìm được.

Sample Input 1:

4
1 2 -5
3 5 6
3 4 -1
4 6 3

Sample Output 1:

8

Explanation 1:

Trọng số lớn nhất là ~8~ bằng cách chọn cặp số ~(3,6)~.

Trọng số của cặp số ~(3,6)~ bằng tổng trọng số của ba đoạn: ~[3,5],[3,4]~ và ~[4,6]~.

Bé Lợi hôm nay đi tập bắn súng. Trong trường súng có ~n~ tấm bia, tấm bia thứ ~i~ bắt đầu ở vị trí ~a_i~ và kết thúc ở vị trí ~b_i~.

Với uy lực của khẩu AK-47, mỗi viên đạn của khẩu súng có đủ uy lực để xuyên qua tất cả các tấm bia nằm trên quỹ đạo của nó. Khi một viên đạn được bắn ở vị trí ~x~, tất cả các tấm bia có ~a_i \leq x \leq b_i~ sẽ được tính là bị bắn trúng.

Hỏi với hai phát bắn, bé Lợi có thể bắn trúng tối đa bao nhiêu tấm bia? Nếu một tấm bia trúng hai phát đạn, nó cũng chỉ được tính 1 lần.

Input

• Dòng đầu nhập số nguyên ~n~ ~(1 \le n \le 10^5)~ là số tấm bia ở trong trường bắn.

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo nhập hai số nguyên ~a_i, b_i~ ~(-10^5 \le a_i < b_i \le 10^5)~ mô tả tấm bia thứ ~i~.

Output

• In ra số lượng tấm bia lớn nhất có thể bị Lợi bắn trúng sau hai phát.

Scoring

• ~30\%~ số test thoả mãn ~n \le 100~.

• ~30\%~ số test khác có ~n \le 1000~.

• ~40\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
1 2
2 3
3 4
4 5
5 6

Sample Output 1

4

Notes

• Lợi bắn vào hai vị trí ~2~ và ~4~. Khi đó tập các tấm bia bắn trúng (đánh số từ ~1~) sẽ là: ~\{1, 2, 3, 4\}~

Xét một xâu có chiều dài ~n~ bao gồm các chữ số ~0~ hoặc ~1~. Điểm của xâu được tính như sau:

• Với mỗi số nguyên ~i~ ~(1 \le i \le m)~, tổng điểm của xâu sẽ được tăng thêm ~a_i~ nếu như xâu con bao gồm các kí tự từ ~l_i~ đến ~r_i~ (kể cả biên) có ít nhất một kí tự ~1~.

Với mọi xâu độ dài ~n~, số điểm cao nhất có thể đạt được là bao nhiêu.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,m~
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i,r_i,a_i~.

Constraints

• ~1 \le n,m \le 2*10^5~
• ~1 \le l_i,r_i \le n, |a_i| \le 10^9~

Subtask :

• Subtask 1: ~n \le 5000~ ~(50\%)~
• Subtask 2: ~n \le 5*10^5~ ~(50\%)~

Output

• In ra số điểm lớn nhất có thể.

Sample Input 1:

5 3
1 3 10
2 4 -10
3 5 10

Sample Output 1:

20

Explanation 2:

• Xâu 10001 là xâu tối ưu.

Sample Input 2:

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

Sample Output 2:

90

Explanation 2:

• Xâu 100 là xâu tối ưu.

Sample Input 3:

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

Sample Output 3:

10

Explanation 3:

• Xâu 101000 là xâu tối ưu.

Thành phố nơi Alice sinh sống có ~n~ toà nhà. Trên bản thiết kế, mặt bằng nền mỗi tòa nhà đều là hình chữ nhật có các cạnh song song với trục tọa độ, với các đỉnh đều có tọa độ nguyên trên hệ trục tọa độ. Hai tòa nhà gọi là liền kề nếu có hai đường biên của hai hình chữ nhật mặt nền tương ứng hai tòa nhà đó có ít nhất một điểm chung. Để thuận tiện đi lại giữa các tòa nhà, người ta xây dựng một lối đi tắt hai chiều giữa mỗi cặp tòa nhà liền kề.

Alice rất thích thú với cách thiết kế các tòa nhà của thành phố và thường xuyên đi lại giữa các tòa nhà thông qua các lối đi tắt này. Sau một thời gian khám phá, Alice nhận thấy có một số lối đi tắt là độc đạo. Một lối đi tắt giữa hai tòa nhà ~u~ và ~v~ gọi là độc đạo nếu như sau khi đi từ ~u~ sang ~v~ qua lối đi này thì không có cách đi nào quay trở lại ~u~ thông qua các lối đi tắt khác ngoài lối đi tắt từ ~v~ về ~u~

Với mỗi cặp tòa nhà ~(u,v)~ có lối đi tắt là độc đạo, Alice tiếp tục khám phá nếu như đóng cửa lối đi độc đạo này thì xuất phát từ ~u~ Alice có thể tham quan được tối đa ~d_u~ tòa nhà và nếu xuất phát từ ~v~, Alice có thể tham quan được tối đa ~d_v~ tòa nhà. Khoảng chênh lệch giữa ~d_u~ và ~d_v~ là giá trị ~|d_u - d_v|~.

Yêu cầu: Biết tọa độ các đỉnh hình chữ nhật mặt nền tương ứng của các tòa nhà, hãy giúp Alice tìm cặp tòa nhà ~(u,v)~ có lối đi tắt độc đạo sao cho khoảng chênh lệch giữa ~d_u~ và ~d_v~ là nhỏ nhất.

Input

• Dòng thứ nhất chứa một số nguyên dương ~n~ là số lượng tòa nhà cao tầng;
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~4~ số nguyên không âm ~x_i,y_i,p_i,q_i~ với ~(x_i,y_i)~ là tọa độ của đỉnh trái trên và ~(p_i,q_i)~ là tọa độ của đỉnh phải dưới của hình chữ nhật biểu thị mặt nền tòa nhà thứ ~i~ trên bản đồ quy hoạch. Dữ liệu đảm bảo ~x_i < p_i~ và ~y_i > q_i~ và hai hình chữ nhật bất kì có thể tiếp xúc nhưng không giao nhau.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là khoảng chênh lệch nhỏ nhất tìm được. Nếu không tồn tại lối đi tắt độc đạo thì in ra số ~-1~.

Constraints

• ~30\%~ số test: ~n \le 10^3~, tọa độ các điểm không quá ~10^9~.
• ~30\%~ số test: ~n \le 10^5~, tọa độ các điểm không quá ~10^3~.
• ~40\%~ số test: ~n \le 10^5~, tọa độ các điểm không quá ~10^9~.

Sample Input 1

6
1 3 4 1
4 1 8 0
6 2 9 1
4 4 8 2
5 6 7 4
6 7 9 6

Sample Output 1

2

Explantion

Các nhà khảo cổ mới phát hiện ra một khu Hoàng Thành được xây dựng từ nhiều thế kỷ trước. Theo nhận định ban đầu, Hoàng Thành gồm nhiều căn phòng khép kín bởi bốn bức tường song song hoặc vuông góc với nhau. Để tiến hành nghiên cứu, các nhà khảo cổ đã xây dựng bản đồ các bức tường của khu Hoàng Thành. Cụ thể, bản đồ được mô tả trên mặt phẳng toạ độ Đề các vuông góc ~Oxy~, trong đó các bức tường là các đoạn thẳng song song với một trong hai trục tọa độ. Theo các dữ liệu thu thập được, có ~n~ căn phòng được đánh số từ ~1~ đến ~n~, căn phòng thứ ~i (1\le i\le n)~ là một hình chữ nhật có tọa độ trái dưới là ~(x_{i},y_{i})~ và tọa độ phải trên là ~(u_{i},v_{i})~. Bốn bức tường tương ứng là các đoạn thẳng nối tọa độ ~(x_{i},y_{i})~ với ~(x_{i},v_{i}), (x_{i},v_{i})~ với ~(u_{i},v_{i}), (u_{i},v_{i})~ với ~(u_{i},y_{i})~ và ~(u_{i},y_{i})~ với ~(x_{i},y_{i})~. Hai đoạn thẳng mô tả hai bức tường của hai phòng khác nhau không có điểm chung. Một thiết bị đặc biệt được các nhà khảo cổ sử dụng để khảo sát khu Hoàng Thành. Thiết bị nhỏ gọn nhưng mỗi khi cần điều khiển thiết bị để vượt qua một bức tường là rất khó khăn. Với một giả định, ban đầu thiết bị được đặt tại tọa độ ~(x_{s},y_{s})~ và cần di chuyển tới tọa độ ~(x_{f},y_{f})~, các nhà khảo cổ muốn tính toán số bức tường ít nhất cần vượt qua khi điều khiển thiết bị.

Yêu cầu: Cho các thông tin về khu Hoàng Thành và ~m~ giả đỉnh, với mỗi giả định hãy giúp các nhà khảo cổ tính toán số bức tường ít nhất cần vượt qua khi điều khiển thiết bị.

Input

• Dòng đầu gồm hai số nguyên dương ~n,m~;
• Dòng thứ ~i (1\le i\le n)~ trong ~n~ dòng tiếp theo gồm bốn số ~x_{i},y_{i},u_{i},v_{i}~ mô tả căn phòng thứ ~i (-10^{9}<x_{i}<u_{i}<10^{9};-10^{9}<y_{i}<v_{i}<10^{9})~;</li>
• Dòng thứ ~j (1\le j\le m)~ trong ~m~ dòng tiếp theo, mỗi dòng mô tả một giả định gồm bốn số nguyên ~x_{s},y_{s},x_{f},y_{f} (-10^{9}<x_{s},y_{s},x_{f},y_{f}<10^{9})~. Điểm ~(x_{s},y_{s} ),(x_{f},y_{f})~ không nằm trên bất kì đoạn thẳng nào mô tả các bức tường của khi Hoàng Thành.</li>

Output

• Ghi ra file thiết bị ra chuẩn gồm m số, mỗi số là đáp án cho truy vấn tương ứng trong dữ liệu vào.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~n,m\le 10^{2}~;
• Subtask ~2~ (~40\%~ số điểm): ~n,m\le 10^{4}~;
• Subtask ~3~ (~30\%~ số điểm): ~n,m\le 10^{6}~.

Example

Sample Input 1

3 2
1 0 6 4
2 1 4 3
7 2 9 5
3 2 8 3
8 3 0 0

Sample Output 1

3
1