After defeating the three sets of twins at the Bandit's Hideout, Leynart will capture the thieves and reward your party with a feast. He will then bid you farewell and give you a bag of "gems" that they had in possession. Yuno will take the bag and ask which of the four stones you would like: Red, Blue, Purple, or Green. Whichever stone you choose will be socketed into your Traveler's Sword, so choose wisely. The Red Stone gives resistance to fire-based attacks and grants you fire power within the sword. The Blue Stone does the same with ice/water, the Purple Stone with lightning, and the Green Stone with Wind. Your sword skills will depend upon your choice.