Amidakuji
Source: aizu

Problem B
Amidakuji

Amidakuji is a method of lottery popular in East Asia. It is often used when a number of gifts are distributed to people or when a number of tasks are assigned.

Figure B-1: An example of amidakuji

Figure B-1 shows an example of amidakuji, which corresponds to the first dataset of Sample Input. A number of vertical lines are drawn. The number of lines is the same as the number of participants. Some number of horizontal bars are drawn between some pairs of adjacent vertical lines. The number and positions of these bars are arbitrary, but no two bars should share their ends. Usually, many horizontal bars are drawn at random.

To use an amidakuji, first, the names of an item, a gift or a task, are written down at the bottom end of vertical lines. Then, each participant chooses the top end of a vertical line, different from one another. Participants trace down the chosen line from the top. When reaching a T-junction with a horizontal bar, that bar is followed, switching to the adjacent vertical line it is connected, and the trace continues downward. When the bottom end of a vertical line is reached, the item written there is the awarded gift or the assigned task. Figure B-2 shows the case when the top end P is chosen. In this case, the item at R is obtained.

Figure B-2: The trace from P

Assume that the participant choosing P of Figure B-2 wants the item at Q, which is not fulfilled. But wait, a special rule just introduced may grant that wish. The new rule allows adding a single horizontal bar at an arbitrary position. Actually, adding a bar marked X in Figure B-3 will make the trace reach Q.

Figure B-3: The new trace after adding a horizontal bar

Your task in this problem is to write a program that finds the position of a horizontal bar to add to the given amidakuji for making the trace starting from the top end of the specified vertical line reach the bottom end of the specified vertical line.

Input

The input consists of multiple datasets, each in the following format.

n m p q
x1 ⋯ xm


All the input items in a dataset are positive integers. n is the number of vertical lines. m is the number of horizontal bars in the original amidakuji. The participant choosing the top end of the p-th line from the left wants the trace to reach the bottom end of the q-th line from the left. You can assume 2 ≤ n ≤ 50, m ≤ 500, p ≤ n, and q ≤ n hold.

x1, ..., and xm give the positions of horizontal bars in the original amidakuji. xk is the position of the k-th bar from the top. Thus, vertical positions of all bars are different. xk ≤ n − 1 holds. The bar connects the xk-th line from the left and the (xk + 1)-th line.

The end of the input is indicated by a line consisting of four zeros. The number of datasets in the input does not exceed 300.

Output

For each dataset, output a single line, which is one of the following.

If q can be reached from p without adding a bar, OK.
If not, and adding a single bar cannot make q reachable from p, NG.
Otherwise, two integers x and y separated by a space, which represent the position of the bar to be added. A bar connecting the x-th line from the left and the (x + 1)-th line should be added at the height between the y-th bar from the top and the (y + 1)-th bar. If the bar is to be added at a position higher than the uppermost bar, y should be 0. If the bar is to be added at a position lower than the lowermost bar, y should be equal to m. If there are two or more appropriate positions to add a bar, the position with the minimum y should be chosen.

OK and NG should be in uppercase.

Sample Input
5 8 3 4
2 1 4 2 3 1 3 2
5 8 3 3
2 1 4 2 3 1 3 2
5 8 3 1
3 1 4 2 2 4 1 3
4 8 1 4
3 1 3 1 3 1 3 1
0 0 0 0

Output for the Sample Input
2 6
OK
NG
2 2


C++ solution:
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    while(true){
        // 入力
        int n, m, p, q;
        cin >> n >> m >> p >> q;
        if(n == 0 && m == 0 && p == 0 && q == 0) break;

        vector<int> X(m);
        for(int i = 0; i < m; i++){
            cin >> X[i];
        }

        int fir = p;
        int proute[m] = {0};
        proute[0] = p;
        int last = q;
        int qroute[m] ={0};
        qroute[0] = q;

        for(int i = 0; i < m; i++){
            if(X[i] == fir){
                fir = X[i]+1;
            }else if(X[i]+1 == fir){
                fir = X[i];
            }

            proute[i+1] = fir;

            if(X[m-1-i] == last){
                last = X[m-1-i] + 1;
            }else if(X[m-1-i] + 1 == last){
                last = X[m-1-i];
            }

            qroute[i+1] = last;
        }

        // for(int i = 0; i <= m; i++){
        //     cout << qroute[i] << endl;
        // }

        if(proute[m] == q){
            cout << "OK" << endl;
        }else{
            bool flag = true;
            for(int i = 0; i <= m; i++){
                if(abs(proute[i] - qroute[m-i]) == 1){
                    cout << min(proute[i],qroute[m-i]) << " " << i << endl;
                    flag = false;
                    break;
                }
            }

            if(flag) cout << "NG" << endl;
        }


    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func drawAmida(x []int, p int) int {
	ed := p
	for _, xi := range x {
		if xi == ed {
			ed += 1
		} else if xi+1 == ed {
			ed -= 1
		}
	}
	return ed
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for {
		var n, m, p, q int
		scanner.Scan()
		line := scanner.Text()
		parts := strings.Fields(line)
		if len(parts) < 4 {
			break
		}
		n, _ = strconv.Atoi(parts[0])
		m, _ = strconv.Atoi(parts[1])
		p, _ = strconv.Atoi(parts[2])
		q, _ = strconv.Atoi(parts[3])
		if n == 0 && m == 0 && p == 0 && q == 0 {
			break
		}
		scanner.Scan()
		xLine := scanner.Text()
		xParts := strings.Fields(xLine)
		x := make([]int, m)
		for i := 0; i < m; i++ {
			x[i], _ = strconv.Atoi(xParts[i])
		}
		if drawAmida(x, p) == q {
			fmt.Println("OK")
			continue
		}
		found := false
	outer:
		for y := 0; y <= m; y++ {
			for j := 1; j < n; j++ {
				var newX []int
				if y == 0 {
					newX = append([]int{j}, x...)
				} else if y >= m {
					newX = append(x, j)
				} else {
					newX = make([]int, len(x)+1)
					copy(newX[:y], x[:y])
					newX[y] = j
					copy(newX[y+1:], x[y:])
				}
				if drawAmida(newX, p) == q {
					fmt.Println(j, y)
					found = true
					break outer
				}
			}
		}
		if !found {
			fmt.Println("NG")
		}
	}
}

Java solution:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            if (n == 0 && m == 0 && p == 0 && q == 0) {
                break;
            }
            int[] x = new int[m];
            for (int i = 0; i < m; i++) {
                x[i] = scanner.nextInt();
            }
            
            int[] l1 = simulate(p, x);
            if (l1[m] == q) {
                System.out.println("OK");
                continue;
            }
            
            int[] reversedX = new int[m];
            for (int i = 0; i < m; i++) {
                reversedX[i] = x[m - 1 - i];
            }
            int[] l2Reversed = simulate(q, reversedX);
            int[] l2 = new int[m + 1];
            for (int i = 0; i <= m; i++) {
                l2[i] = l2Reversed[m - i];
            }
            
            boolean found = false;
            for (int i = 0; i <= m; i++) {
                if (Math.abs(l1[i] - l2[i]) == 1) {
                    int min = Math.min(l1[i], l2[i]);
                    System.out.println(min + " " + i);
                    found = true;
                    break;
                }
            }
            if (!found) {
                System.out.println("NG");
            }
        }
        scanner.close();
    }
    
    private static int[] simulate(int start, int[] x) {
        int[] path = new int[x.length + 1];
        int current = start;
        path[0] = current;
        for (int i = 0; i < x.length; i++) {
            int bar = x[i];
            if (current == bar) {
                current = bar + 1;
            } else if (current == bar + 1) {
                current = bar;
            }
            path[i + 1] = current;
        }
        return path;
    }
}

JavaScript solution:
const readline = require('readline');

function drawAmida(x, p) {
    let ed = p;
    for (let i = 0; i < x.length; i++) {
        if (x[i] === ed) {
            ed += 1;
        } else if (x[i] + 1 === ed) {
            ed -= 1;
        }
    }
    return ed;
}

async function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
        terminal: false
    });

    const lines = [];
    for await (const line of rl) {
        lines.push(line.trim());
    }

    let idx = 0;
    while (idx < lines.length) {
        const firstLine = lines[idx++].split(' ').map(Number);
        const [n, m, p, q] = firstLine;
        
        if (n === 0 && m === 0 && p === 0 && q === 0) break;

        const x = lines[idx++].split(' ').map(Number);

        const result = drawAmida(x, p);
        if (q === result) {
            console.log("OK");
            continue;
        }

        let found = false;
        outer: for (let i = 0; i <= m; i++) {
            for (let j = 1; j < n; j++) {
                let v;
                if (i === 0) {
                    v = [j, ...x];
                } else if (i >= m) {
                    v = [...x, j];
                } else {
                    v = [...x.slice(0, i), j, ...x.slice(i)];
                }
                if (q === drawAmida(v, p)) {
                    console.log(j, i);
                    found = true;
                    break outer;
                }
            }
        }

        if (!found) {
            console.log("NG");
        }
    }
}

main().catch(err => console.error(err));

Python solution:
def f(now, x):
    l = [now]
    for i in x:
        if now == i:
            now = i + 1
        elif now == i + 1:
            now = i
        l.append(now)
    return l

while True:
    n, m, p, q = map(int, input().split())
    if n == m == p == q == 0:
        break
    x = list(map(int, input().split()))
    l1 = f(p, x)
    if l1[-1] == q:
        print('OK')
        continue
    l2 = f(q, x[::-1])[::-1]
    for i in range(m + 1):
        if abs(l1[i] - l2[i]) == 1:
            print(min(l1[i], l2[i]), i)
            break
    else:
        print('NG')

Ruby solution:
def trace_path(bars, start)
  current = start
  bars.each do |bar|
    if bar == current
      current += 1
    elsif bar == current - 1
      current -= 1
    end
  end
  current
end

def main
  while true
    # Read first line (n, m, p, q)
    line = gets
    break if line.nil? || line.strip.empty?
    
    n, m, p, q = line.strip.split.map(&:to_i)
    break if n == 0 && m == 0 && p == 0 && q == 0
    
    # Read second line (horizontal bars)
    bars = gets.strip.split.map(&:to_i)
    
    # Check if already OK
    if q == trace_path(bars, p)
      puts "OK"
      next
    end
    
    found = false
    # Try inserting at all possible positions (0..m)
    (0..m).each do |insert_pos|
      # Try all possible bar values (1..n-1)
      (1...n).each do |new_bar|
        # Create new configuration with inserted bar
        new_bars = if insert_pos == 0
                    [new_bar] + bars
                  elsif insert_pos >= m
                    bars + [new_bar]
                  else
                    bars[0...insert_pos] + [new_bar] + bars[insert_pos..-1]
                  end
        
        # Check if this configuration works
        if q == trace_path(new_bars, p)
          puts "#{new_bar} #{insert_pos}"
          found = true
          break
        end
      end
      break if found
    end
    
    puts "NG" unless found
  end
end

main