Програмчлалын олимпиадын бодлогын архив

Бөмбөг ашиглан тоглох нэг тоглоом доор үзүүлсэн сонгогчуудаас тогтоно:

         Баруун төлөв                       Зүүн төлөв
           |       |                         |       |                     
           |       |                         |       |
           |       |                         |       |
          / \       \                       /       / \
         /   \       \                     /       /   \
        /     \       \                   /       /     \
       /       O       \                 /       O       \
      /       / \       \               /       / \       \
     /       /   \       \             /       /   \       \         

Бөмбгийг сонгогчийн дээд талаас оруулна. Сонгогчийн голд байгаа хаалт бөмбгийг зүүн тал руу өнхрөх үү, баруун тал руу өнхрөх үү гэдгийг шийднэ. Бөмбөг өнхөрч гарсны дараа хаалт байрлалаа өөрчлөнө. Жишээ нь дээр үзүүлсэн баруун төлөвтөө байгаа сонгогчид орсон бөмбөг баруун тал руу өнхөрч гарах ба үүний дараа хаалт байрлалаа өөрчлөх тул уг сонгогчид дараагийн удаа ирсэн бөмбөг зүүн тал руу өнхөрч гарах болно. Дээр зурсан зүүн төлөвт байгаа сонгогчийн хувьд яг эсрэгээрээ байна. Бид олон сонгогчуудыг хоолойгоор холбон сүлжээ үүсгэж болно. Жишээ нь: {"L 1 2","R 2 0","L X X"} Энэ нь 0 дугаартай сонгогч зүүн төлөвтөө тоглоомыг эхэлнэ гэсэн үг. Түүний зүүн тал нь сонгогч 1-тэй холбогдсон, баруун тал нь сонгогч 2-той холбогдсон. Сонгогч 1 тоглоомыг баруун төлөвт эхэлнэ. Түүний зүүн тал нь сонгогч 2-той, баруун тал нь сонгогч 0-тэй холбогдсон. Сонгогч 2 нь тоглоомын эхэнд зүүн төлөвтөө байх ба түүний зүүн болон баруун тал нь тоглоомыг дуусгана. Хэрэв бөмбөгийг сонгогч 0-д оруулбал тэр тоглоомоос гарах хүртлээ нийт 4-н сонгогчийг дайрч өнгөрнө(0-р сонгогч дараа нь 1-р, дараа нь 0, эцэст нь 2). Сонгогчдын сүлжээ болон бөмбөгийг оруулах сонгогчийг өгсөн бол бөмбөг тоглоомыг орхих хүртлээ хэдэн сонгогчийг дамжихыг ол. Хэрэв бөмбөг тоглоомыг хэзээ ч орхихгүй бол -1-ийг буцаана. Тоглоом нь 1-15 сонгогч агуулж болно.

Input

Оролтын файлын эхний мөрөнд тоглоом дахь сонгогчийн тоо N байна. Дараагийн N мөрөнд сонгогчуудын тухай мэдээлэл:
dir left right
гэсэн форматаар өгөгдөнө.Энэ гурав нь хоорондоо зайгаар тусгаарлагдсан. dir нь сонгогчийн эхлэх төлвийг заах ба 'L' (зүүн) эсвэл 'R' (баруун) үсэг байна. left болон right нь 'X' үсэг юм уу эсвэл [0, N-1] завсраас утгаа авах бүхэл тоо байх ба сонгогчийн зүүн болон баруун тал нь өөр ямар сонгогчтой холбогдсоныг харгалзан илэрхийлнэ. 'X' нь тоглоомыг орхих талыг заана.
Үүний дараа сүүлийн мөрөнд аль сонгогчид бөмбөг эхэлж орохыг заасан бүхэл тоо байна.

Output

Гаралтан дээр бөмбөгийн дайрч өнгөрөх сонгогчдын тоо эсвэл бөмбөг хэзээ ч гарахгүй тохиолдолд -1 гэсэ тоо байна.

Example

Input:
3
L 1 2
R 2 0
L X X
0
Output:
4
Тайлбар: Бөмбөг 0->1->0->2 дарааллаар өнхөрнө.