B - Postdocs /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

英大文字 P および D からなる文字列 S について、S が連続する部分文字列として含む D および PD の個数の和を S の「博士・PD 指数」と呼びます。例えば S = PPDDP のとき、S は連続する部分文字列として 2 個の D1 個の PD を含んでいるので、S の博士・PD 指数は 3 です。

P, D, ? からなる文字列 T があります。

T に含まれる ? をそれぞれ P または D のいずれかで置き換えてできる文字列の中で、博士・PD 指数が最大のものを 1 つ求めてください。

制約

  • 1 \leq |T| \leq 2 \times 10^5
  • TP, D, ? からなる。

入力

入力は以下の形式で標準入力から与えられる。

T

出力

T に含まれる ? をそれぞれ P または D で置き換えてできる文字列の中で、博士・PD 指数が最大のものを 1 つ出力せよ。 そのような文字列が複数ある場合、どれを出力しても構わない。


入力例 1

PD?D??P

出力例 1

PDPDPDP

この文字列は連続する部分文字列として 3 個の D3 個の PD を含みます。 よってこの文字列の博士・PD 指数は 6 です。 T に含まれる ? をそれぞれ P または D で置き換えてできる文字列の中で、これは最大の博士・PD 指数です。


入力例 2

P?P?

出力例 2

PDPD

Score : 200 points

Problem Statement

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.


Sample Input 1

PD?D??P

Sample Output 1

PDPDPDP

This string contains three occurrences of D and three occurrences of PD as contiguous substrings, so its doctoral and postdoctoral quotient is 6, which is the maximum doctoral and postdoctoral quotient of a string obtained by replacing each ? in T with P or D.


Sample Input 2

P?P?

Sample Output 2

PDPD