Trộn Hai Luồng Chữ Số · canuc80k0437

Cho một xâu $s$ chỉ gồm các chữ số thập phân. Trong một thao tác, bạn được đổi chỗ hai chữ số kề nhau nếu một chữ số chẵn và chữ số kia lẻ.

Bạn có thể thực hiện thao tác bao nhiêu lần tùy ý. Hãy tìm xâu nhỏ nhất theo thứ tự từ điển có thể nhận được. Các số $0$ ở đầu xâu vẫn được giữ nguyên và tham gia so sánh như mọi chữ số khác.

Input

Dòng đầu chứa số nguyên $t$ - số bộ dữ liệu.
Mỗi bộ dữ liệu gồm một dòng chứa xâu chữ số $s$ .

Output

Với mỗi bộ dữ liệu, in ra xâu nhỏ nhất có thể nhận được.

Constraints

$1 \leq t \leq 1 0^{4}$ .
$1 \leq ∣ s ∣ \leq 3 \cdot 1 0^{5}$ .
Mỗi ký tự của $s$ thuộc từ '0' đến '9'.
Tổng độ dài các xâu qua tất cả bộ dữ liệu không vượt quá $3 \cdot 1 0^{5}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): Mỗi xâu có độ dài không vượt quá $12$ và tổng độ dài không vượt quá $50$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

0279
86420
012345

Giải thích: Với $7092$ , thứ tự tương đối của $0, 2$ và của $7, 9$ phải được giữ, nhưng hai dãy có thể trộn thành $0279$ ; xâu $86420$ chỉ có chữ số chẵn nên không đổi được, còn $135024$ cho phép trộn thành $012345$ .

Ý tưởng: Hai chữ số cùng tính chẵn lẻ không bao giờ được đổi chỗ trực tiếp. Mọi thao tác chỉ cho một chữ số chẵn đi qua một chữ số lẻ, nên thứ tự tương đối của các chữ số chẵn được giữ nguyên; điều tương tự đúng với các chữ số lẻ.
Ý tưởng: Ngược lại, mọi cách trộn hai dãy con đó mà vẫn giữ thứ tự nội bộ đều thực hiện được bằng các phép đổi chỗ kề nhau khác tính chẵn lẻ. Vì vậy tập kết quả đúng là tập các phép trộn ổn định của:
Ý tưởng: dãy các chữ số chẵn theo thứ tự xuất hiện;
Ý tưởng: dãy các chữ số lẻ theo thứ tự xuất hiện.
Ý tưởng: Để lấy phép trộn nhỏ nhất từ điển, ở mỗi vị trí chọn chữ số nhỏ hơn ở đầu hai dãy. Nếu chọn chữ số lớn hơn trong khi chữ số nhỏ hơn đang sẵn sàng, vị trí đầu tiên khác nhau đã làm kết quả tệ hơn và các lựa chọn sau không thể sửa lại.
Ý tưởng: Thuật toán chạy trong O(|s|) thời gian và dùng O(|s|) bộ nhớ cho mỗi xâu.