Problem: There is a string s, consisting of capital Latin letters. Let's denote its current length as |s|. During one move it is allowed to apply one of the following operations to it: 

  * INSERT pos ch — insert a letter ch in the string s in the position pos (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z). The letter ch becomes the pos-th symbol of the string s, at that the letters shift aside and the length of the string increases by 1. 
  * DELETE pos — delete a character number pos (1 ≤ pos ≤ |s|) from the string s. At that the letters shift together and the length of the string decreases by 1. 
  * REPLACE pos ch — the letter in the position pos of the line s is replaced by ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z). At that the length of the string does not change. 



Your task is to find in which minimal number of moves one can get a t string from an s string. You should also find the sequence of actions leading to the required results.

Input

The first line contains s, the second line contains t. The lines consist only of capital Latin letters, their lengths are positive numbers from 1 to 1000.

Output

In the first line print the number of moves k in the given sequence of operations. The number should be the minimal possible one. Then print k lines containing one operation each. Print the operations in the format, described above. If there are several solutions, print any of them.

Examples

Input

ABA
ABBBA


Output

2
INSERT 3 B
INSERT 4 B


Input

ACCEPTED
WRONGANSWER


Output

10
REPLACE 1 W
REPLACE 2 R
REPLACE 3 O
REPLACE 4 N
REPLACE 5 G
REPLACE 6 A
INSERT 7 N
INSERT 8 S
INSERT 9 W
REPLACE 11 R

Solution (in JAVA):

Solution:
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.ObjectInputStream.GetField;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	static PrintWriter out;
	static Scanner sc;
	static int n,w,ws[],T,ptr[][],k,m;
	static long mem[][],v[],d[];
	static boolean tk[],dv;
	static long oo=(long)1e9+7;
	static Boolean dp[][];
	static String s,t;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
		//B();
		//C();
		//D();
		E();
		//F();
		//G();
		out.close();
	}
	  private static void A() throws IOException {
		  n=ni();
		  w=ni();
		  ws=new int[n]; 
		  v=new long[n];
		  for(int i=0;i<n;i++){
			  ws[i]=ni();
			  v[i]=nl();
		  }
		  mem=new long[n][w+1];
		  for(int i=0;i<n;i++)Arrays.fill(mem[i], -1);
		  long ans=kn(0,0);
		  ol(""+ans);
	   }
	
		private static long kn(int i, int sum) {
		if(i==n)return 0;
		if(mem[i][sum]!=-1)return mem[i][sum];
		long ch1=kn(i+1,sum);
		long ch2=0;
		if(sum+ws[i]<=w) {
			ch2=v[i]+kn(i+1,sum+ws[i]);
		}
		return mem[i][sum]=Math.max(ch1, ch2);
	}
		static void B() throws IOException {
			int k=0;
			while(sc.ready()) {
				if(k==0)k=1;else ol("");
				T=ni();w=ni();
				n=ni();
				d=new long[n];v=new long[n];
				ptr=new int[n][T+1];
				for(int i=0;i<n;i++) {
					d[i]=nl();
					v[i]=nl();
				}
				mem=new long[n][T+1];
				for(int i=0;i<n;i++)Arrays.fill(mem[i], -1);
				tk=new boolean[n];
				long ans=div(0,0);
				ol(""+ans);
				bck();
				int cnt=0;
				for(int i=0;i<n;i++)if(tk[i])cnt++;
				ol(cnt);
				for(int i=0;i<n;i++) {
					if(tk[i]) {
						ol(d[i]+" "+v[i]);
					}
				}
				
			}
		}
		private static void bck() {
			for(int i=0,t=0;i<n&&t<=T;i++) {
				int cur=ptr[i][t];
				if(cur==2) {
					tk[i]=true;
					t+=3*w*d[i];
				}
			}
		}
		private static long div(int i, int t) {
			if(i==n)return 0;
			if(mem[i][t]!=-1)return mem[i][t];
			long ch1=div(i+1,t);
			long ch2=0;
			if(t+3*d[i]*w<=T) {
				ch2=v[i]+div(i+1,(int)(t+3*d[i]*w));
			}
			ptr[i][t]=ch2>ch1?2:1;
			return mem[i][t]=Math.max(ch1, ch2);
		}
		static void C() throws IOException{
			int h=ni(),w=ni();
			mem=new long[h][w];
			char[][]mp=new char[h][w];
			for(int i=0;i<h;i++) {
				mp[i]=ns().toCharArray();
			}
			for(int i=0;i<h;i++) {
				if(mp[i][0]!='.')break;
				mem[i][0]=1;
			}
			for(int i=0;i<w;i++) {
				if(mp[0][i]!='.')break;
				mem[0][i]=1;
			}
			
			for(int i=1;i<h;i++){
				for(int j=1;j<w;j++){
					if(mp[i][j]!='.')continue;
					mem[i][j]=(mem[i-1][j]+mem[i][j-1])%oo;
					//mem[i][j]=(mem[i][j]+2)%oo;
				}
			}
			ol(""+mem[h-1][w-1]);
			
		}
	
		static void D() throws IOException {
			int tc=ni();
			while(tc-->0) {
				n=ni();k=ni();
				dp=new Boolean[n][k];
				d=nal(n);
				out.println(solve(1,mod(d[0],k))?
						"Divisible":"Not divisible");
			}
		}
		
		
		
	private static int mod(long l,int k) {
			return (int) ((l%k + k)%k);
		}
	private static boolean solve(int i, int j) {
			if(i==n)return j==0;
			if(dp[i][j]!=null)return dp[i][j];
			return dp[i][j]=solve(i+1,mod(j+d[i],k))
					| solve(i+1,mod(j-d[i],k));
		}
	static void E() throws IOException {
		s=ns();
		t=ns();
		n=s.length();
		m=t.length();
		mem=new long[s.length()][t.length()];
		ptr=new int[s.length()][t.length()];
		for(int i=0;i<mem.length;i++)Arrays.fill(mem[i], -1);
		out.println(lv(0,0));
		steps();
	}

	private static void steps() {
		int cur=1;
		for(int i=0,j=0;i<n||j<m;) {
			if(i==n||j<m&&ptr[i][j]==1) {
				ol("INSERT "+(i+cur++)+" "+t.charAt(j));
				j++;
			}else if(j==m||i<n&&ptr[i][j]==2) {
				ol("DELETE "+(i+cur--));
				i++;
			}else {
				if(s.charAt(i)!=t.charAt(j)) {
					ol("REPLACE "+(i+cur)+" "+t.charAt(j));
				}
				i++;j++;
			}
		}
	}
	
	private static long lv(int i, int j) {
		if(i==n)return m-j;
		if(j==m)return n-i;
		if(mem[i][j]!=-1)return mem[i][j];
		long ch1=1+lv(i,j+1);
		long ch2=1+lv(i+1,j);
		long ch3=lv(i+1,j+1)+(s.charAt(i)==t.charAt(j)?0:1);
		long ans=Math.min(ch1, Math.min(ch2, ch3));
		ptr[i][j]=ans==ch1?1:ans==ch2?2:3;
		return mem[i][j]=ans;
	}
	static void F() throws IOException {
		
	}
	static void G() throws IOException {
		
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}