#include <iostream>
#include <vector>
using namespace std;


vector<vector<int>> weave(vector<int> lhs,
                          vector<int> rhs,
                          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(lhs_short, rhs, 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;
}





// To execute C++, please define "int main()"
int main() {

vector<int> lhs = {1,3,5,7,9};
vector<int> rhs = {0,2,4,6,8};
  auto out = weave(rhs,lhs);
  for(auto items: out)
  {
    cout << "{ ";
    for(auto item: items)
    {
      cout << item << " ";
    }
    cout << "}" << endl;
  }
  return 0;
}