// #pragma GCC optimize("O3,unroll-loops") #include // #include using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif struct fast_fourier_transform_wrapper{ using CD = complex; using CLD = complex; // i \in [2^k, 2^{k+1}) holds w_{2^k+1}^{i-2^k} static vector root; static vector root_ld; static void adjust_root(int n){ if(root.empty()) root = {1, 1}, root_ld = {1, 1}; for(auto k = (int)root.size(); k < n; k <<= 1){ root.resize(n), root_ld.resize(n); auto theta = polar(1.0L, acos(-1.0L) / k); for(auto i = k; i < k << 1; ++ i) root[i] = root_ld[i] = i & 1 ? root_ld[i >> 1] * theta : root_ld[i >> 1]; } } // O(n * log(n)) static void transform(vector &p, bool invert = false){ int n = (int)p.size(); assert(n && __builtin_popcount(n) == 1); for(auto i = 1, j = 0; i < n; ++ i){ int bit = n >> 1; for(; j & bit; bit >>= 1) j ^= bit; j ^= bit; if(i < j) swap(p[i], p[j]); } adjust_root(n); for(auto len = 1; len < n; len <<= 1) for(auto i = 0; i < n; i += len << 1) for(auto j = 0; j < len; ++ j){ auto x = (double *)&root[j + len], y = (double *)&p[i + j + len]; CD z(x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0]); p[len + i + j] = p[i + j] - z, p[i + j] += z; } if(invert){ reverse(p.begin() + 1, p.end()); auto inv_n = 1.0l / n; for(auto &x: p) x *= inv_n; } } static vector buffer1, buffer2; // O(n * m) template static vector convolute_naive(const vector &p, const vector &q){ vector res(max((int)p.size() + (int)q.size() - 1, 0)); for(auto i = 0; i < (int)p.size(); ++ i) for(auto j = 0; j < (int)q.size(); ++ j) res[i + j] += p[i] * q[j]; return res; } // Safe for sum(p[i]^2 + q[i]^2) lg2(n) < 9e14 // O(n * log(n)) template static vector convolute(const vector &p, const vector &q){ if(min(p.size(), q.size()) < 60) return convolute_naive(p, q); int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1; buffer1.assign(n, 0); for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i].real(p[i]); for(auto i = 0; i < (int)q.size(); ++ i) buffer1[i].imag(q[i]); transform(buffer1); for(auto &x: buffer1) x *= x; buffer2.assign(n, 0); for(auto i = 0; i < n; ++ i) buffer2[i] = buffer1[i] - conj(buffer1[-i & n - 1]); transform(buffer2, true); vector res((int)p.size() + (int)q.size() - 1); for(auto i = 0; i < (int)res.size(); ++ i) res[i] = is_integral_v ? llround(buffer2[i].imag() / 4) : buffer2[i].imag() / 4; return res; } // O(n * log(n)) static vector convolute_complex(const vector &p, const vector &q){ if(min(p.size(), q.size()) < 60) return convolute_naive(p, q); int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1; buffer1 = p, buffer2 = q; buffer1.resize(n), buffer2.resize(n); transform(buffer1), transform(buffer2); for(auto i = 0; i < n; ++ i) buffer1[i] *= buffer2[i]; transform(buffer1, true); return {buffer1.begin(), buffer1.begin() + ((int)p.size() + (int)q.size() - 1)}; } // Safe for 64-bit integer range // O(n * log(n)) template static vector convolute_splitting(const vector &p, const vector &q){ if(min(p.size(), q.size()) < 80) return convolute_naive(p, q); int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1; const int cut = 32000; buffer1.assign(n, 0); for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i] = {(int)p[i] / cut, (int)p[i] % cut}; transform(buffer1); buffer2.assign(n, 0); for(auto i = 0; i < (int)q.size(); ++ i) buffer2[i] = {(int)q[i] / cut, (int)q[i] % cut}; transform(buffer2); for(auto i = 0; i <= n >> 1; ++ i){ int j = -i & n - 1; if(i == j){ tie(buffer1[i], buffer2[i]) = pair{ (buffer1[i] + conj(buffer1[i])) * buffer2[i] / 2.0, (buffer1[i] - conj(buffer1[i])) * buffer2[i] / 2i }; } else{ tie(buffer1[i], buffer2[i], buffer1[j], buffer2[j]) = tuple{ (buffer1[i] + conj(buffer1[j])) * buffer2[i] / 2.0, (buffer1[i] - conj(buffer1[j])) * buffer2[i] / 2i, (buffer1[j] + conj(buffer1[i])) * buffer2[j] / 2.0, (buffer1[j] - conj(buffer1[i])) * buffer2[j] / 2i }; } } transform(buffer1, true); transform(buffer2, true); vector res((int)p.size() + (int)q.size() - 1); for(auto i = 0; i < (int)res.size(); ++ i) res[i] = ((T)llround(buffer1[i].real()) * cut + (T)(llround(buffer1[i].imag()) + llround(buffer2[i].real()))) * cut + (T)llround(buffer2[i].imag()); return res; } // Safe for 64-bit integer range // O(n * log(n)) template static vector convolute_splitting_mod(const vector &p, const vector &q){ if(min(p.size(), q.size()) < 80) return convolute_naive(p, q); vector p2(p.begin(), p.end()), q2(q.begin(), q.end()); p2 = convolute_splitting(p2, q2); return {p2.begin(), p2.end()}; } }; vector> fast_fourier_transform_wrapper::root; vector> fast_fourier_transform_wrapper::root_ld; vector> fast_fourier_transform_wrapper::buffer1; vector> fast_fourier_transform_wrapper::buffer2; using fft = fast_fourier_transform_wrapper; int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n, qn; cin >> n >> qn; const int base = 101; vector a(base * base * base); for(auto i = 0; i < n; ++ i){ int x, y, z; cin >> x >> y >> z; a[base * base * x + base * y + z] = 1; } auto b = a; ranges::reverse(b); auto ab = fft::convolute(a, b); int res = 0; for(auto qi = 0; qi < qn; ++ qi){ int x, y, z; cin >> x >> y >> z; res = max(res, 2 * n - ab[base * base * base - 1 + base * base * x + base * y + z]); } cout << res << "\n"; return 0; } /* */