// rotates a vector in place by x items to the right (can't rotate by negatives at the moment)
// it can be applied to strings if you convert a string to a char vector
template<class t>
void rotate(vector<t> &vec, int x) {
    x = ((x % vec.size()) + vec.size()) % vec.size();
    vector<t> new_vec;
    for (int i = vec.size() - x; i < (signed) vec.size(); i++) {
        new_vec.push_back(vec[i]);
    }
    for (int i = 0; i < (signed) vec.size() - x; i++) {
        new_vec.push_back(vec[i]);
    }
    vec = new_vec;
}