#pragma GCC optimize("unroll-loops, O3")
#include <bits/stdc++.h>
#include "cheat.h"
using namespace std;
using pii = pair<int, int>;
using point = pii;
using segment = pair<pii, pii>;
int dp[8]; // dp de contagem, quantos números consigo fazer
vector<vector<int>> bit, brute;
vector<vector<segment>> segs;
map<segment, int> id;
bool to_init = true;
void print(segment s){
// cout << "(" << s.first.first << " " << s.first.second << ") - (" << s.second.first << ", " << s.second.second << ")\n";
}
segment to_seg(int x){
return segs[x / 4][x % 4];
}
point rotate(point p){
return {2 - p.second, p.first};
}
segment rotate(segment s){
segment r = {rotate(s.first), rotate(s.second)};
if(r.first > r.second) swap(r.first, r.second);
return r;
}
int rotate(int mask){
int nmask = 0;
for(int i=0; i<28; i++){
if(mask & (1 << i)){
int j = id[rotate(to_seg(i))];
nmask += (1 << j);
}
}
return nmask;
}
void add(segment s, vector<vector<segment>> &segs){
segs.push_back({});
for(int i=0; i<4; i++){
segs.back().push_back(s);
s = rotate(s);
}
}
void add(int s, vector<int> &rot){
for(int i=0; i<4; i++){
rot.push_back(s);
s = rotate(s);
}
}
void init(){
bit.push_back({}); brute.push_back({});
for(int pos=1; pos<=7; pos++){
bit.push_back({0, 0, 0, 0});
for(int i=0; i<4; i++) bit[pos][i] = (1 << (4 * (pos - 1) + i));
brute.push_back({});
brute[pos] = {0, bit[pos][0] + bit[pos][1] + bit[pos][2] + bit[pos][3], bit[pos][0] + bit[pos][2], bit[pos][1] + bit[pos][3]};
}
dp[0] = 0;
for(int i=1; i<=7; i++) dp[i] = 3 * (1 << 4 * (i - 1)) + 4 * dp[i - 1];
id.clear();
segs.clear();
add({{0, 0}, {0, 1}}, segs);
add({{0, 0}, {1, 0}}, segs);
add({{0, 0}, {1, 1}}, segs);
add({{0, 0}, {2, 1}}, segs);
add({{0, 1}, {1, 0}}, segs);
add({{0, 1}, {2, 0}}, segs);
add({{1, 0}, {1, 1}}, segs);
for(int i=0; i<7; i++){
for(int j=0; j<4; j++){
id[segs[i][j]] = 4 * i + j;
}
}
}
int encode(int n, int pos){
int x = (1 << (4 * (pos - 1)));
if(n < 3 * x){
if(n < x) return n + bit[pos][0];
if(n < 2 * x) return (n - x) + bit[pos][0] + bit[pos][1];
return (n - 2 * x) + bit[pos][1] + bit[pos][2] + bit[pos][3];
}
n -= 3 * x;
int cnt = dp[pos - 1];
return encode(n - (n / cnt) * cnt, pos - 1) + brute[pos][n / cnt];
}
int decode(int mask, int pos){
int x = (1 << (4 * (pos - 1)));
int cur = 0;
for(int i=0; i<4; i++) if(mask & bit[pos][i]) cur += bit[pos][i];
int id = -1;
for(int i=0; i<4; i++) if(cur == brute[pos][i]) id = i;
if(id != -1) return id * dp[pos - 1] + 3 * x + decode(mask, pos - 1);
int cnt = __builtin_popcount(cur) - 1;
int b = 4 * (pos - 1);
mask &= (1 << b) - 1;
return mask + cnt * x;
}
int getRotation(int mask, int pos){
int cur = 0;
for(int i=0; i<4; i++) if(mask & bit[pos][i]) cur += bit[pos][i];
for(int i=0; i<4; i++) if(cur == brute[pos][i]) return getRotation(mask, pos - 1);
int cur_rot = 0, cnt = __builtin_popcount(cur) - 1;
vector<int> rot;
if(cnt == 0) add(bit[pos][0], rot);
if(cnt == 1) add(bit[pos][0] + bit[pos][1], rot);
if(cnt == 2) add(bit[pos][1] + bit[pos][2] + bit[pos][3], rot);
int b = 4 * (pos - 1);
for(int j=0; j<4; j++) if((cur >> b) == (rot[j] >> b)) cur_rot = 4 - j;
return cur_rot;
}
vector<segment> BuildPattern(int n){
if(to_init) init();
to_init = false;
int mask = encode(n, 7);
vector<segment> ret;
for(int i=0; i<28; i++){
if(mask & (1 << i)){
ret.push_back(to_seg(i));
}
}
return ret;
}
int GetCardNumber(vector<segment> p){
if(to_init) init();
to_init = false;
int mask = 0;
for(auto &s : p){
if(s.first > s.second) swap(s.first, s.second);
mask += (1 << id[s]);
}
int rot = getRotation(mask, 7);
for(int j=0; j<rot; j++) mask = rotate(mask);
mask = decode(mask, 7);
int n = 0;
for(int i=0; i<28; i++) if(mask & (1 << i)) n += (1 << i);
return n;
}
