#include<bits/stdc++.h>
#define ll long long
// input: 2 points
// output: (a, b, c) represents the equation: ax + by = c
template <typename T> vector<T> line_passing_2_points(T x1, T y1, T x2, T y2) {
T a = y2 - y1;
T b = x1 - x2;
T c = a*(x1) + b*(y1);
T gcd;
gcd = __gcd(a, b);
gcd = __gcd(gcd, c);
a/= gcd;
b/= gcd;
c/= gcd;
if (a < 0) {
a = -a;
b = -b;
c = -c;
}
vector<T> line = {a, b, c};
return line;
}