Problem: For a string S consisting of the uppercase English letters `P` and `D`, let the doctoral and postdoctoral quotient of S be the total number of occurrences of `D` and `PD` in S as contiguous substrings. For example, if S = `PPDDP`, it contains two occurrences of `D` and one occurrence of `PD` as contiguous substrings, so the doctoral and postdoctoral quotient of S is 3.

We have a string T consisting of `P`, `D`, and `?`.

Among the strings that can be obtained by replacing each `?` in T with `P` or `D`, find one with the maximum possible doctoral and postdoctoral quotient.

Constraints

* 1 \leq |T| \leq 2 \times 10^5
* T consists of `P`, `D`, and `?`.

Input

Input is given from Standard Input in the following format:


T


Output

Print one string with the maximum possible doctoral and postdoctoral quotient among the strings that can be obtained by replacing each `?` in T with `P` or `D`. If there are multiple such strings, you may print any of them.

Examples

Input

PD?D??P


Output

PDPDPDP


Input

P?P?


Output

PDPD

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	char[] T, result;
	int N;

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	Main(BufferedReader in) throws IOException {
		T = in.readLine().toCharArray();
		N = T.length;
		result = new char[N];
	}

	void init() {
		// 最初を埋める
		if (T[0] == '?') {
			if (T[1] == '?') {
				result[0] = 'P';
			} else if (T[1] == 'P') {
				result[0] = 'D';
			} else {
				result[0] = 'P';
			}
		} else {
			result[0] = T[0];
		}
	}

	void calc() {
		if (N == 1) {
			if (T[0] == '?') {
				System.out.println('D');
			} else {
				System.out.println(T[0]);
			}
		} else {
			init();
			for (int i = 1; i + 1 < N; ++i) {
				if (result[i - 1] == 'P') {
					if (T[i] == '?') {
						result[i] = 'D';
					} else {
						result[i] = T[i];
					}
				} else {
					if (T[i] == '?') {
						if (T[i + 1] == '?' || T[i + 1] == 'D') {
							result[i] = 'P';
						} else {
							result[i] = 'D';
						}
					} else {
						result[i] = T[i];
					}
				}
			}
			if (T[N - 1] == '?') {
				result[N - 1] = 'D';
			} else {
				result[N - 1] = T[N - 1];
			}
			for (int i = 0; i < N; ++i) {
				System.out.print(result[i]);
			}
			System.out.println("");
		}
	}

	void showResult() {
	}
}