NKROBOT - Robot quét vôi

no tags 

Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với màu trắng, xanh hoặc vàng. Có 9 robot (đánh số từ 1 đến 9) phụ trách việc quét vôi. Mỗi robot chỉ quét một số phòng nhất định. Việc quét vôi được thực hiện nhờ một chương trình cài sẵn theo qui tắc:

  • Nếu phòng đang có màu trắng thì quét màu xanh
  • Nếu phòng đang có màu xanh thì quét màu vàng
  • Nếu phòng đang có màu vàng thì quét màu trắng

Cần phải gọi lần lượt một số các robot ra quét vôi (mỗi lần một robot, một robot có thể gọi nhiều lần và có thể có robot không được gọi. Robot được gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng các phòng đều có màu trắng.

Yêu cầu: Hãy tìm một phương án như vậy sao cho số lần gọi robot là ít nhất. Giả thiết rằng lượng vôi cho mỗi lượt quét đối với các phòng là như nhau.

Input

  • 9 dòng đầu: dòng thứ i mô tả một danh sách các phòng do robot i phụ trách việc quét vôi. Mỗi dòng là một chuỗi các chữ số từ 1..9 biểu diễn các số hiệu của các phòng, các chữ số viết sát nhau.
  • Dòng cuối mô tả mầu vôi ban đầu của các phòng. Dòng gồm 9 ký tự viết sát nhau gồm toàn các chữ cái T (trắng), X (xanh), V(vàng) biểu diễn mầu ban đầu của 9 căn phòng theo trật tự số hiệu của chúng.

Output

gồm một dòng

  • Nếu không có phương án thì in ra số 0
  • Trái lại thì in ra dãy thứ tự các robot được gọi (số hiệu các robot được viết sát nhau)

Example

Input:

159

123

357

147

5

369

456

789

258

XVXVXVTXT


Output:
2455688


Added by:Vương Trung Hiếu Nghĩa
Date:2010-08-06
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:Sưu tầm