숫자 맞추기

N개의 회전 가능한 숫자나사가 위에서 아래로 이어져 있습니다. 가장 위의 숫자나사는 1번, 가장 아래의 숫자나사는 N번입니다. 각 숫자나사에는 10개의 면이 있고, 각 면에는 오른쪽 방향으로 0, 1, 2, ..., 9가 차례대로 적혀 있습니다.

어떤 숫자나사를 왼쪽으로 돌리면 그 숫자나사와 그 아래에 있는 모든 숫자나사가 함께 돌아갑니다. 반대로 오른쪽으로 돌리면 그 숫자나사만 돌아가고 다른 숫자나사는 움직이지 않습니다.

정면에서 위에서 아래로 읽은 현재 상태와 목표 상태가 주어질 때, 총 회전 칸수가 최소가 되도록 목표 상태를 만드는 회전 방법을 출력하세요.

첫째 줄에 숫자나사의 개수 N이 주어집니다. 둘째 줄에는 현재 상태를 나타내는 길이 N의 숫자 문자열이, 셋째 줄에는 목표 상태를 나타내는 길이 N의 숫자 문자열이 주어집니다.

N은 3 이상 10,000 이하입니다.

첫째 줄에 현재 상태에서 목표 상태로 도달하는 데 필요한 최소 회전 칸수를 출력합니다. 다음 줄부터는 회전 순서대로 한 줄에 하나씩 숫자나사 번호와 회전 칸수를 빈칸으로 구분해 출력합니다.

회전 칸수는 왼쪽 방향을 양수로 표현합니다. 왼쪽으로 4칸 돌리는 경우는 4, 오른쪽으로 3칸 돌리는 경우는 -3을 출력합니다. 가능한 답이 여러 개라면 그중 아무 하나를 출력해도 됩니다.