vector<vector<int>> weave(vector<int> rhs,
                          vector<int> lhs,
                          vector<int> prefix = vector<int>())
{
  vector<vector<int>> output;
  if(rhs.empty())
  {
    auto single = prefix;
    single.insert(single.end(), lhs.begin(), lhs.end());
    output.push_back(single);
  }
  else if (lhs.empty())
  {
    auto single = prefix;
    single.insert(single.end(), rhs.begin(), rhs.end());
    output.push_back(single);
  }
  else
  {
    // LHS
    auto lhs_short = lhs;
    auto lhs_prefix = prefix;
    lhs_prefix.push_back(lhs_short.front());
    lhs_short.erase(lhs_short.begin());
    auto lhs_weaved = weave(rhs, lhs_short, lhs_prefix);
    output.insert(output.end(), lhs_weaved.begin(), lhs_weaved.end());
    // RHS
    auto rhs_short = rhs;
    auto rhs_prefix = prefix;
    rhs_prefix.push_back(rhs_short.front());
    rhs_short.erase(rhs_short.begin());
    auto rhs_weaved = weave(lhs, rhs_short, rhs_prefix);
    output.insert(output.end(), rhs_weaved.begin(), rhs_weaved.end());
  }
  return output;
}