C ++ implementation of the above approach
#include <bits/stdc++.h> NEW_LINE #define mp  make_pair NEW_LINE #define pb  push_back NEW_LINE #define S  second NEW_LINE #define ll  long long NEW_LINE using namespace std ;