1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e6 + 5, M = 1e6 + 5;
6
int n;
7
vector<int> pos;
8
vector<pair<int, int>> a[M];
9

10
class Point {
11
 public:
12
  int x, y, w;
13
} points[N];
14

15
class SegmentTree {
16
  class Values {
17
   public:
18
    long long max, add;
19
    int index;
20
  };
21

22
  class Node {
23
   public:
24
    int left, right;
25
    Values val;
26

27
    Node() = default;
28
    Node(int l, int r) : left(l), right(r), val() {}
29
  };
30

31
  Node tr[M << 2];
32

33
  static int get_lc(int k) { return k << 1; }
34
  static int get_rc(int k) { return k << 1 | 1; }
35
  int get_mid(int k) { return (tr[k].left + tr[k].right) >> 1; }
36

37
  void make_lazy_add(int k, long long val) {
38
    tr[k].val.add += val;
39
    tr[k].val.max += val;
40
  }
41

42
  void push_up(int k) {
43
    int lc = get_lc(k), rc = get_rc(k);
44

45
    if (tr[lc].val.max > tr[rc].val.max) {
46
      tr[k].val.max = tr[lc].val.max;
47
      tr[k].val.index = tr[lc].val.index;
48
    } else {
49
      tr[k].val.max = tr[rc].val.max;
50
      tr[k].val.index = tr[rc].val.index;
51
    }
52
  }
53

54
  void push_down(int k) {
55
    if (tr[k].val.add == 0)
56
      return void();
57

58
    int lc = get_lc(k), rc = get_rc(k);
59

60
    make_lazy_add(lc, tr[k].val.add);
61
    make_lazy_add(rc, tr[k].val.add);
62

63
    tr[k].val.add = 0;
64
  }
65

66
 public:
67
  void build_tree(int k, int l, int r) {
68
    tr[k] = Node(l, r);
69

70
    if (tr[k].left == tr[k].right) {
71
      tr[k].val.max = -pos[l - 1];
72
      tr[k].val.index = l;
73
      return void();
74
    }
75

76
    int mid = get_mid(k);
77
    int lc = get_lc(k), rc = get_rc(k);
78

79
    build_tree(lc, l, mid);
80
    build_tree(rc, mid + 1, r);
81

82
    push_up(k);
83
  }
84

85
  void modify(int k, int l, int r, int val) {
86
    if (tr[k].left >= l && tr[k].right <= r) {
87
      make_lazy_add(k, val);
88
      return void();
89
    }
90

91
    push_down(k);
92

93
    int mid = get_mid(k);
94
    int lc = get_lc(k), rc = get_rc(k);
95

96
    if (r <= mid) {
97
      modify(lc, l, r, val);
98
    } else if (l > mid) {
99
      modify(rc, l, r, val);
100
    } else {
101
      modify(lc, l, mid, val);
102
      modify(rc, mid + 1, r, val);
103
    }
104

105
    push_up(k);
106
  }
107

108
  pair<long long, long long> query(int k, int l, int r) {
109
    if (tr[k].left >= l && tr[k].right <= r) {
110
      return make_pair(tr[k].val.max, tr[k].val.index);
111
    }
112

113
    push_down(k);
114

115
    int mid = get_mid(k);
116
    int lc = get_lc(k), rc = get_rc(k);
117

118
    if (r <= mid) {
119
      return query(lc, l, r);
120
    } else if (l > mid) {
121
      return query(rc, l, r);
122
    } else {
123
      return max(query(lc, l, mid), query(rc, mid + 1, r));
124
    }
125
  }
126
} seg;
127

128
int get_index(int val) {
129
  return lower_bound(pos.begin(), pos.end(), val) - pos.begin() + 1;
130
}
131

132
int main() {
133
  ios::sync_with_stdio(false);
134
  cin.tie(nullptr);
135
  cout.tie(nullptr);
136

137
  cin >> n;
138

139
  for (int i = 1; i <= n; i ++) {
140
    cin >> points[i].x >> points[i].y >> points[i].w;
141

142
    pos.emplace_back(points[i].x);
143
    pos.emplace_back(points[i].y);
144

145
    if (points[i].x > points[i].y) {
146
      swap(points[i].x, points[i].y);
147
    }
148
  }
149

150
  sort(pos.begin(), pos.end());
151
  pos.erase(unique(pos.begin(), pos.end()), pos.end());
152

153
  int limit = 0;
154
  for (int i = 1; i <= n; i ++) {
155
    points[i].x = get_index(points[i].x);
156
    points[i].y = get_index(points[i].y);
157

158
    limit = max(limit, points[i].y);
159

160
    a[points[i].x].emplace_back(points[i].y, points[i].w);
161
  }
162

163
  seg.build_tree(1, 1, limit);
164

165
  long long answer = -1ll << 60, left = 0, right = 0;
166
  for (int line = limit; line >= 1; line --) {
167
    for (auto p : a[line]) {
168
      seg.modify(1, p.first, limit, p.second);
169
    }
170

171
    pair<long long, long long> result = seg.query(1, line, limit);
172
    result.first += pos[line - 1];
173

174
    if (result.first > answer) {
175
      answer = result.first;
176
      left = pos[line - 1];
177
      right = pos[result.second - 1];
178
    }
179
  }
180

181
  if (answer < 0) {
182
    answer = 0;
183
    left = 1e9 + 1, right = 1e9 + 1;
184
  }
185

186
  cout << answer << "\n";
187
  cout << left << " " << left << " " << right << " " << right << '\n';
188

189
  return 0;
190
}

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e5 + 5;
6
bool satisfied[N];
7
int n, m, k, u, v, l, r;
8

9
class DSU {
10
  int fa[N << 1], size[N << 1];
11
  stack<pair<int *, int>> stk;
12

13
 public:
14
  void init(int limit) {
15
    for (int i = 1; i <= limit; i++) fa[i] = i, size[i] = 1;
16
  }
17

18
  int find(int x) {
19
    if (fa[x] != x) return find(fa[x]);
20
    return x;
21
  }
22

23
  void merge(int u, int v) {
24
    u = find(u);
25
    v = find(v);
26
    if (u == v) return void();
27

28
    if (size[u] > size[v]) swap(u, v);
29

30
    stk.emplace(fa + u, fa[u]);
31
    stk.emplace(size + v, size[v]);
32
    fa[u] = v;
33
    size[v] += size[u];
34
  }
35

36
  bool check(int x, int y) { return find(x) == find(y); }
37

38
  int get_version() { return stk.size(); }
39

40
  void undo(int version) {
41
    while (stk.size() > version) {
42
      *stk.top().first = stk.top().second;
43
      stk.pop();
44
    }
45
  }
46
} d;
47

48
class SegmentTree {
49
  class Node {
50
   public:
51
    int left, right;
52
    vector<pair<int, int>> edges;
53

54
    Node() = default;
55
    Node(int l, int r) : left(l), right(r) { edges.clear(); }
56
  };
57

58
  Node tr[N << 2];
59

60
  static int get_lc(int k) { return k << 1; }
61
  static int get_rc(int k) { return k << 1 | 1; }
62
  int get_mid(int k) { return (tr[k].left + tr[k].right) >> 1; }
63

64
 public:
65
  void build_tree(int k, int l, int r) {
66
    tr[k] = Node(l, r);
67

68
    if (tr[k].left == tr[k].right) {
69
      return void();
70
    }
71

72
    int mid = get_mid(k);
73
    int lc = get_lc(k), rc = get_rc(k);
74

75
    build_tree(lc, l, mid);
76
    build_tree(rc, mid + 1, r);
77
  }
78

79
  void add_edge(int k, int l, int r, pair<int, int> edge) {
80
    if (tr[k].left >= l && tr[k].right <= r) {
81
      tr[k].edges.emplace_back(edge);
82
      return void();
83
    }
84

85
    int mid = get_mid(k);
86
    int lc = get_lc(k), rc = get_rc(k);
87

88
    if (r <= mid) {
89
      add_edge(lc, l, r, edge);
90
    } else if (l > mid) {
91
      add_edge(rc, l, r, edge);
92
    } else {
93
      add_edge(lc, l, mid, edge);
94
      add_edge(rc, mid + 1, r, edge);
95
    }
96
  }
97

98
  void dfs(int k) {
99
    bool flag = true;
100
    int version = d.get_version();
101

102
    for (auto edge : tr[k].edges) {
103
      if (d.check(edge.first, edge.second)) {
104
        flag = false;
105
        break;
106
      } else {
107
        d.merge(edge.first, edge.second + n);
108
        d.merge(edge.first + n, edge.second);
109
      }
110
    }
111

112
    if (flag == false) {
113
      for (int i = 1; i <= tr[k].right - tr[k].left + 1; i++) {
114
        cout << "No\n";
115
      }
116
    } else {
117
      if (tr[k].left == tr[k].right) {
118
        cout << "Yes\n";
119
      } else {
120
        int lc = get_lc(k), rc = get_rc(k);
121

122
        dfs(lc);
123
        dfs(rc);
124
      }
125
    }
126

127
    d.undo(version);
128
  }
129
} seg;
130

131
int main() {
132
  ios::sync_with_stdio(false);
133
  cin.tie(nullptr);
134
  cout.tie(nullptr);
135

136
  cin >> n >> m >> k;
137

138
  d.init(n << 1);
139
  seg.build_tree(1, 1, k);
140

141
  for (int i = 1; i <= m; i++) {
142
    cin >> u >> v >> l >> r;
143

144
    if (l == r) continue;
145
    seg.add_edge(1, l + 1, r, make_pair(u, v));
146
  }
147

148
  seg.dfs(1);
149

150
  return 0;
151
}